单链表双链表中经常纠结的概念：
1、链表是否有含有头结点：
（1）带头结点的链表头指针head指向头结点，数据域不含任何信息，只是指向链表的第一个保存信息的结点，head->next等于null则表示链表为空；
（2）不带头结点的链表头指针head直接指向保存信息的第一个结点，head==null，表示链表为空。
说道这里，有人会对头指针，头结点的概念迷糊了。。。
头指针：指向链表的第一个结点，不管是不是带头结点的；
头结点：只针对带头结点的链表而言，只作为链表存在的标志，不含信息。
一般建立链表最好用带头结点的。
1 #include <stdio.h> 2 #include <stdlib.h> 3 typedef struct Lnode//单链表结点 4 { 5 int data; 6 struct Lnode *next; 7 }Lnode; 8 9 typedef struct Dnode//双链表结点 10 { 11 int data; 12 struct Dnode *next,*prior; 13 }Dnode; 14 15 int main() 16 { 17 void CreateListByTail(Lnode *c,int a[],int length);//尾插法建立单链表 18 void CreateListByHead(Lnode *c,int a[],int length);//头插法建立单链表 19 void CreateDListByTail(Dnode *c,int a[],int length);//尾插法建立双链表 20 void CreateDListByHead(Dnode *c,int a[],int length);//头插法建立双链表 21 void MergeTwoList(Lnode *A,Lnode *B);//合并两个按顺序排列的单链表，不创建新结点 22 int SearchAndDeleteList(Lnode *list,int x);//单链表查找与x相等的第一个元素并删除 23 int SearchAndDeleteDList(Dnode *list,int x);//双链表查找与x相等的第一个元素并删除 24 void PrintList(Lnode *list);//输出单链表数据 25 void PrintDList(Dnode *dlist);//输出双链表数据 26 Lnode *list; 27 Lnode *listA; 28 Dnode *dlist; 29 list=(Lnode*)malloc(sizeof(Lnode)); 30 listA=(Lnode*)malloc(sizeof(Lnode)); 31 dlist=(Dnode*)malloc(sizeof(Dnode)); 32 list->next=NULL; 33 listA->next=NULL; 34 dlist->next=NULL; 35 int a[5]={1,2,6,8,12}; 36 int b[4]={3,7,9,10}; 37 CreateListByTail(list,a,5); 38 //CreateDListByHead(dlist,a,5); 39 PrintList(list); 40 //PrintDList(dlist); 41 CreateListByTail(listA,b,4); 42 PrintList(listA); 43 printf("after list&dlist merged：\n"); 44 MergeTwoList(list,listA); 45 PrintList(list); 46 //SearchAndDeleteList(list,4); 47 //SearchAndDeleteDList(dlist,4); 48 //PrintList(list); 49 //PrintDList(dlist); 50 return 0; 51 } 52 void CreateListByHead(Lnode *c,int a[],int length) 53 { 54 Lnode *p; 55 int i=0; 56 for(i=0;i<length;i++) 57 { 58 p=(Lnode*)malloc(sizeof(Lnode)); 59 p->data=a[i]; 60 p->next=c->next; 61 c->next=p; 62 } 63 } 64 void CreateListByTail(Lnode *c,int a[],int length) 65 { 66 int i=0; 67 Lnode *n,*p;//n是每次新的结点，p是前一个结点 68 p=c; 69 for(i=0;i<length;i++) 70 { 71 n=(Lnode*)malloc(sizeof(Lnode)); 72 n->data=a[i]; 73 n->next=p->next; 74 p->next=n; 75 p=n; 76 } 77 } 78 79 void CreateDListByTail(Dnode *c,int a[],int length) 80 { 81 int i=0; 82 Dnode *n,*p; 83 p=c; 84 for(i=0;i<length;i++) 85 { 86 n=(Dnode*)malloc(sizeof(Dnode)); 87 n->data=a[i]; 88 n->next=p->next; 89 n->prior=p; 90 p->next=n; 91 p=n; 92 } 93 } 94 void CreateDListByHead(Dnode *c,int a[],int length) 95 { 96 Dnode *p; 97 int i=0; 98 for(i=0;i<length;i++) 99 { 100 p=(Dnode*)malloc(sizeof(Dnode)); 101 p->data=a[i]; 102 p->next=c->next; 103 c->next=p; 104 p->prior=c; 105 } 106 } 107 int SearchAndDeleteDList(Dnode *dlist,int x) 108 { 109 Dnode *p,*q; 110 p=dlist; 111 while(p->next!=NULL) 112 { 113 if(p->next->data==x) 114 break; 115 else p=p->next; 116 } 117 if(p->next==NULL) 118 return 0; 119 else 120 { 121 q=p->next; 122 p->next=q->next; 123 q->next->prior=p; 124 free(q); 125 return 1; 126 } 127 } 128 int SearchAndDeleteList(Lnode *list,int x) 129 { 130 Lnode *p,*q; 131 p=list; 132 while(p->next!=NULL) 133 { 134 if(p->next->data==x) 135 break; 136 else p=p->next; 137 } 138 if(p->next==NULL) 139 return 0; 140 else 141 { 142 q=p->next; 143 p->next=q->next; 144 free(q); 145 return 1; 146 } 147 } 148 void PrintList(Lnode *list) 149 { 150 Lnode *p; 151 p=list->next; 152 printf("This single list is:\n"); 153 while(p!=NULL) 154 { 155 printf("%3d",p->data); 156 p=p->next; 157 } 158 printf("\n"); 159 } 160 void PrintDList(Dnode *dlist) 161 { 162 Dnode *p; 163 p=dlist->next; 164 printf("This double list is:\n"); 165 while(p!=NULL) 166 { 167 printf("%3d",p->data); 168 p=p->next; 169 } 170 printf("\n"); 171 } 172 173 //合并两个按顺序排列的单链表，合成结果是A链表 174 void MergeTwoList(Lnode *A,Lnode *B) 175 { 176 Lnode *p=A->next; 177 Lnode *q=B->next; 178 Lnode *r; 179 r=A; 180 r->next=NULL; 181 free(B); 182 while(p!=NULL&&q!=NULL) 183 { 184 if(p->data<=q->data) 185 { 186 r->next=p; 187 p=p->next; 188 r=r->next; 189 } 190 else 191 { 192 r->next=q; 193 q=q->next; 194 r=r->next; 195 } 196 } 197 r->next=NULL; 198 if(p!=NULL) 199 r->next=p; 200 else r->next=q; 201 }
未完待续。。。