单链表的基本操作
- 2019 年 10 月 5 日
- 笔记
实现单链表的增加删除定位等功能。（编译执行环境vc6.0，因为目标院校上机考是用这个版本的）
1 #include<stdio.h> 2 #include<malloc.h> 3 #include<stdlib.h> 4 #include<time.h> 5 6 7 typedef struct LNode 8 { 9 int data; 10 struct LNode *next; 11 }LNode; 12 13 //初始化单链表 14 int initList(LNode *&L) 15 { 16 L = (LNode *)malloc(sizeof(LNode)); 17 L->next = NULL; 18 printf("链表初始化成功n"); 19 return 1; 20 } 21 22 23 //给定一个单链表初值，后续每个结点为累计+3赋值 ，长度为n（头插法） 24 int InsertList(LNode *L, int s ,int n) 25 { 26 if(n<1) 27 { 28 printf("请输入正确的长度！！"); 29 return 0; 30 } 31 //t用来指向新生成的节点 32 LNode *t; 33 34 int p=0; 35 int q=s; 36 while(p<n) 37 { 38 t=(LNode *)malloc(sizeof(LNode)); 39 t->data=q; 40 t->next=L->next; 41 L->next=t; 42 q-=3; 43 p++; 44 } 45 return 1; 46 47 } 48 49 50 //给定一个单链表初值，后续每个结点为累计+3赋值 ，长度为n（尾插法） 51 int InsertList2(LNode *L, int s ,int n) 52 { 53 if(n<1) 54 { 55 printf("请输入正确的长度！！"); 56 return 0; 57 } 58 //t用来指向新生成的节点 59 LNode *t,*r; 60 r=L; 61 62 int q=s; 63 for(int i=0;i<n;i++) 64 { 65 t=(LNode*)malloc(sizeof(LNode)); 66 t->data=q; 67 r->next=t; 68 r=r->next; 69 q+=3; 70 } 71 r->next=NULL; 72 return 1; 73 74 } 75 //遍历链表 76 void OutList(LNode *L) 77 { 78 LNode *p; 79 p=L->next; 80 while(p) 81 { 82 printf("%3d n",p->data); 83 p=p->next; 84 } 85 } 86 //实现a，b两个有序链表的有序拼接，拼接后为串c 87 void merge(LNode *a,LNode *b,LNode *&c) 88 { 89 LNode *p=a->next; 90 LNode *q=b->next; 91 LNode *r; 92 c=a; 93 c->next=NULL; 94 free(b); 95 r=c; 96 while(p!=NULL && q!=NULL) 97 { 98 if(p->data<=q->data) 99 { 100 r->next=p; 101 p=p->next; 102 r=r->next; 103 } 104 else 105 { 106 r->next=q; 107 q=q->next; 108 r=r->next; 109 } 110 } 111 r->next=NULL; 112 if(p!=NULL) 113 r->next=p; 114 if(q!=NULL) 115 r->next=q; 116 } 117 //查找链表中是否存在值为x的元素，若存在则删除，否则返回0 118 int findAndDelete(LNode *L,int x) 119 { 120 LNode *p,*q; 121 p=L; 122 while(p->next!=NULL) 123 { 124 if(p->next->data==x) 125 break; 126 p=p->next; 127 128 } 129 if(p->next==NULL) 130 { 131 return 0; 132 } 133 else 134 { 135 q=p->next; 136 p->next=p->next->next; 137 free(q); 138 return 1; 139 } 140 } 141 void main() 142 { 143 LNode *L; 144 LNode *t; 145 LNode *L1; 146 initList(L); 147 initList(L1); 148 if(InsertList2(L,5,5)==1) 149 { 150 printf("赋值成功n"); 151 }else 152 printf("赋值失败"); 153 if(InsertList(L1,30,5)==1) 154 { 155 printf("赋值成功n"); 156 }else 157 printf("赋值失败"); 158 159 merge(L1,L,t); 160 OutList(t); 161 findAndDelete(t,5); 162 OutList(t); 163 164 }
