2）线性链表

　　线性表的顺序存储的缺点非常明显：我们插入和删除时，需要移动大量的元素，这显然将耗费很长的时间。
　　当线性表的长度变化较大时，相对来说难以确定存储空间的容量。

因此，为解决上述问题，提出了线性表的链式存储结构。

引用：

1.http://blog.csdn.net/u011314012/article/details/49069377

2.http://www.cnblogs.com/fanyong/archive/2011/11/06/2238439.html

3. 大话数据结构

1. 链式存储结构

　　链表中的第一个结点的存储位置叫做头指针，最后一个结点指针域为空(NULL)。链表中的头结点不是链表的必要元素。

下面介绍下头结点和头指针的区别(参见大话数据结构P59)：

1)头指针是指向链表中第一个结点的指针，若链表有头结点，则是头指针---是指向头结点的指针。

2)无论链表是否为空，头指针都不为空。头指针是链表的必要元素，而头结点不是。

3)头结点的数据域一般不存储任何信息。

2. 代码

  1 #include <iostream>
  2 
  3 using namespace std;
  4 
  5 
  6 
  7 typedef int ElemType;
  8 typedef struct _tag_LinkListNode LinkListNode;//
  9 
 10 struct _tag_LinkListNode
 11 {
 12  LinkListNode *next;
 13 };
 14 
 15 //0. linklist的存储结构
 16 typedef struct Node
 17 {
 18     ElemType data;
 19     //int length;
 20     struct Node *next;
 21 } Node;
 22 
 23 typedef struct _tag_LinkList
 24 {
 25     LinkListNode head;
 26     int length;
 27 }LinkList;
 28 
 29 
 30 //1. 创建线性表
 31  LinkList* initList()
 32 {
 33     int ret=0;
 34     LinkList *tmp=(LinkList*)malloc(sizeof(LinkList));
 35     if(tmp==NULL)
 36     {
 37         ret=-1;
 38         printf("initList erro: %d",ret);
 39     }
 40     
 41     //(*tmp)->length=0;
 42     memset(tmp,0,sizeof(LinkList));
 43     if(tmp!=NULL)
 44     {
 45         tmp->head.next=NULL;
 46         tmp->length=0;
 47     }
 48     return tmp;
 49 }
 50 
 51 //2. 销毁线性表
 52 void LinKList_Destory(LinkList* list)
 53 {
 54     if(list!=NULL)
 55     {
 56         free(list);
 57         list=NULL;
 58     }
 59     return;
 60 }
 61 
 62 //3. 清空链表所有元素，恢复初始状态
 63 void LinkList_Clear(LinkList* list)
 64 {
 65     LinkList* sList = (LinkList*)list;
 66  
 67     if(sList != NULL)
 68     {
 69          sList->length = 0;
 70          sList->head.next = NULL;
 71     } 
 72 }
 73 
 74 
 75 //4 .插入
 76 int LinkList_Insert(LinkList* list,int pos,LinkListNode *node)
 77 {
 78     int ret=0;
 79     LinkListNode *current=NULL;
 80 
 81     if(list==NULL||pos<0||node==NULL)
 82     {
 83         ret=-1;
 84         printf("LinkList_Insert ()erro: %d",ret);
 85         return ret;
 86     }
 87 
 88     current=&(list->head);
 89 
 90     for(int i=0;i<pos&&current->next!=NULL;i++)
 91     {
 92         current=current->next;
 93     }
 94     
 95     node->next=current->next;//1 node连接后续链表
 96     current->next=node;    //2 连接节点
 97     list->length++;
 98     return 0;
 99 }
100 
101 // 5. 删除，返回该节点
102 LinkListNode * LinkList_Delete(LinkList* list,int pos)
103 {
104     int ret=0;
105     LinkListNode *node=NULL;
106     LinkListNode *current=NULL;
107 
108     if(list==NULL||pos<0)
109     {
110         ret=-1;
111         printf("LinkList_Insert ()erro: %d",ret);
112         return (LinkListNode * )ret ;
113     }
114 
115     current=&(list->head);
116     
117     for(int i=0;i<pos&&(current->next!=NULL);i++)
118     {
119         current=current->next;
120     }
121     node=current->next;//1 缓存node节点
122 
123      //2 连接节点
124     current->next=node->next;   
125     list->length--;
126 
127     return node;
128 }
129 
130 //6. 获取线性表的元素
131 LinkListNode * getElem(LinkList *list,int i)
132 {
133     LinkListNode *node=NULL;
134     node=&(list->head);
135     for(int k=0;k<=i;k++)
136     {
137         node=node->next;
138     }
139     return node;
140 }

3. 测试代码

 1 int main()
 2 {
 3     int ret=0;
 4     typedef struct Teacher
 5     {
 6         LinkListNode node;//第一个域是node，就可以把teacher强制转化为LinkListNode
 7         int age;
 8     }Teacher;
 9 
10     LinkList *list1=NULL;
11 
12     Teacher t1,t2,t3,t4,t5;
13     t1.age=31;
14     t2.age=32;
15     t3.age=33;
16     t4.age=34;
17     t5.age=35;
18     
19 
20     list1=initList();
21     if(list1==NULL)
22     {
23         return -1;
24     }
25 
26     //1.插入：int LinkList_Insert(LinkList* list,int pos,LinkListNode *node)
27     ret=LinkList_Insert(list1,0,(LinkListNode*)(&t1));
28     ret=LinkList_Insert(list1,0,(LinkListNode*)(&t2));
29     ret=LinkList_Insert(list1,0,(LinkListNode*)(&t3));
30     ret=LinkList_Insert(list1,0,(LinkListNode*)(&t4));
31     ret=LinkList_Insert(list1,0,(LinkListNode*)(&t5));
32 
33 
34     //2. 遍历LinkListNode * getElem(LinkList *list,int i)
35     printf("
输入值: 
");
36     for (int i=0;i<list1->length;i++)
37     {
38         Teacher *tmp=(Teacher*)getElem(list1,i);
39         if(tmp==NULL)
40         {
41             return -2;
42         }
43         printf("tmp->age :%d 
",tmp->age);
44     }
45 
46     //3. 删除 int LinkList_Delete(LinkList* list,int pos,LinkListNode *node)
47         printf("
删除: 
");
48         LinkListNode *node=NULL;
49         
50         while(list1->length>0)
51         {
52             LinkListNode *node=LinkList_Delete(list1,0);//头删法
53             Teacher *teacher=(Teacher*)node;
54             if(teacher==NULL)
55             {
56                 return -2;
57             }
58             printf("tmp->age :%d 
",teacher->age);
59         }
60     system("pause");
61     return 0;
62 }

4. 运行结果

2） 线性链表

2）线性链表