C语言实现双向链表的插入、删除、查找运算
1 #include2 #include 3 #include 4 5 typedef int ElemType; 6 typedef struct DLnode 7 { 8 ElemType data; //定义数据域 9 struct DLnode *prior; //定义前驱结点 10 struct DLnode *next; //定义后继结点 11 }DLnode,*DLinkList; //定义结点和头指针类型名 12 13 void Init_DLinkList(DLinkList &L) 14 { //初始化链表 15 L = (DLnode *)malloc(sizeof(DLnode)); //生成头结点 16 L->prior = L->next = NULL; //初始化头、尾结点 17 } 18 19 void Create_DLinkList(DLinkList &L,int n) 20 { //前插法创建双向链表 21 int i; 22 DLinkList p; 23 L = (DLinkList)malloc(sizeof(DLnode)); 24 L->next = NULL; //生成头结点 25 L->prior = NULL; 26 for (i = n; i > 0; --i) 27 { 28 p = (DLinkList)malloc(sizeof(DLnode)); //生成新结点 29 p->data = i; //装填数据 30 p->next =L->next; //将*p插入原开始结点之前，头结点之后 31 L->next = p; 32 if (p->next != NULL) 33 p->next->prior = p; 34 p->prior = L; 35 } 36 } 37 38 int Locate_DLinkList(DLinkList L,ElemType e) 39 { //在双向链表中查找某个数据元素 40 int i = 1; 41 DLinkList p = L->next; 42 while(p != NULL && p->data != e) 43 { 44 i ++; 45 p = p->next; 46 } 47 if (p == NULL) 48 { 49 printf("双链表中不存在该元素！\n"); 50 return 0; 51 } 52 else 53 return i; 54 } 55 56 int Insert_DLinkList(DLinkList &L,int i,ElemType e) 57 { //在第i个数据元素之前插入新元素 58 int j = 0; 59 DLinkList p = L, s; 60 while (p != NULL && j < i) 61 { 62 j ++; 63 p = p->next; 64 } 65 if (p == NULL) //第i个结点不存在 66 { 67 printf("插入位置不正确!\n"); 68 return 0; 69 } 70 else //找到第i个结点*p 71 { 72 s = (DLnode *)malloc(sizeof(DLnode)); //生成新结点*s 73 s->data = e; 74 s->prior = p->prior; //将*s插入到*p之前 75 s->next = p; 76 p->prior->next = s; 77 p->prior = s; 78 return 1; 79 } 80 } 81 82 int Delete_DLinkList(DLinkList &L,int i,ElemType &e) 83 { //删除链表中第i个数据元素 84 int j = 0; 85 DLinkList p = L; 86 while(j < i && p != NULL) 87 { 88 j ++; 89 p = p->next; 90 } 91 if (p == NULL) 92 { 93 printf("删除位置不正确!\n"); 94 return 0; 95 } 96 else 97 { 98 e = p->data; 99 p->prior->next = p->next; //删除*p结点100 if (p->next != NULL)101 p->next->prior = p->prior;102 free(p);103 return 1;104 }105 }106 107 void Display_DLinkList(DLinkList L)108 {109 DLinkList p;110 p = L->next;111 while(p)112 {113 printf("%d ",p->data);114 p = p->next;115 }116 }117 118 int main(int argc, char * argv[])119 {120 DLinkList L;121 int i,j,e,x,t;122 char ch;123 Init_DLinkList(L);124 Create_DLinkList(L,10);125 printf("初始化\n建立双向链表如下\n");126 Display_DLinkList(L);127 while (i < 10)128 {129 printf("\n 主菜单 \n");130 printf(" 1 查找指定元素 \n");131 printf(" 2 插入元素到指定位置 \n");132 printf(" 3 删除某一指定位置元素 \n");133 printf(" 4 退出程序 \n");134 printf("----------------------------------------------\n");135 printf("请输入你选择的单号<1,2,3,4>: ");136 scanf("%d",&i);137 switch(i)138 {139 case 1:140 printf("请输入查找元素: ");141 scanf("%d",&x);142 j = Locate_DLinkList(L,x);143 if (j != 0)144 printf("指定元素位置 = %d\n",j);145 break;146 case 2:147 printf("请输入插入元素位置后结点序号: ");148 scanf("%d",&t);149 printf("请输入插入元素值: ");150 scanf("%d",&x);151 j = Insert_DLinkList(L,t,x);152 if (j != 0)153 {154 printf("插入后双向链表如下所示:\n");155 Display_DLinkList(L);156 }157 break;158 case 3:159 printf("请输入删除元素位置: ");160 scanf("%d",&t);161 j = Delete_DLinkList(L,t,e);162 if (j != 0)163 {164 printf("删除后双向链表如下所示:\n");165 Display_DLinkList(L);166 }167 break;168 case 4:169 exit(0);170 break;171 default:172 printf("输入有误!");173 }174 }175 }
运行结果
