001 ////////////////////////////////////////////
002 //双链表的初始化，建立，插入，查找，删除。//
003 //Author:Wang Yong //
004 //Date: 2010.8.19 //
005 ////////////////////////////////////////////
006
007
008 #include <stdio.h>
009 #include <stdlib.h>
010
011 typedef int ElemType;
012 ////////////////////////////////////////////
013
014 // 定义双链表结点类型
015
016 typedef struct Node
017 {
018 ElemType data;
019 struct Node *prior; //指向前驱结点
020 struct Node *next; //指向后继结点
021 }Node, *DLinkList;
022
023 ////////////////////////////////////////////
024
025 //双链表的建立，采用尾插法建立双链表
026 DLinkList DLinkListCreatT()
027 {
028 Node *L,*p,*r;
029 L = (Node *)malloc(sizeof(Node));//申请头结点
030 L->next = NULL;
031 r = L;
032 r->next = NULL; //r 为指向终端结点的指针
033 ElemType x;
034 while(scanf("%d",&x) != EOF) //输入双链表元素，建立双链表
035 {
036 p = (Node *)malloc(sizeof(Node));
037 p->data = x;
038 p->next = r->next;
039 r->next = p;
040 r = p;
041 }
042 r->next = NULL;
043 return L;
044 }
045
046 /////////////////////////////////////////
047
048 //双链表的查找，查找元素为x的位置
049
050 int DLinkListFind(DLinkList L,ElemType x)
051 {
052 DLinkList p; //p为检索，
053 p = L->next;
054 int i = 1;
055 while(p != NULL && p->data != x )//寻找值为x的元素**注意这里循环的条件不能写反
056 { //原因，当p == NULL 时候 p->data 会出错
057 ++i; // for (i = 1, p = L->next; p; p = p->next, i++) {
058 // if (p->data == x) break;}
059 p = p->next;
060 }
061
062 if(p == NULL) //如果没找到返回0
063 return 0;
064 else return i; //如果找到返回i
065 }
066 /////////////////////////////////////////
067
068 //双链表的插入，在双链表中的第i个位置插入值为x的元素
069
070 DLinkList DLinkListInsert(DLinkList L,int i,ElemType x)
071 {
072 DLinkList p,s; //s为要插入的结点
073 p = L->next; //从第一个结点位置开始查找
074 int tempi;
075 for(tempi = 1;tempi < i-1; tempi++)
076 p = p->next;
077 s = (Node *)malloc(sizeof(Node));
078 s->data = x; //将x赋值到s的数据域
079 s->next = p->next; //将结点插入
080 p->next->prior = s;
081 s->prior = p;
082 p->next = s;
083
084 return L;
085
086 }
087
088 //////////////////////////////////////////////
089
090 //双链表的删除，删除双链表中第i个结点
091
092 DLinkList DLinkListDelete(DLinkList L,int i)
093 {
094 int tempi = 1;
095 DLinkList p; //p为查找结点。
096 p = L->next;
097 while((tempi++) != i && p != NULL)
098 {
099 p = p->next;
100 }
101 if(p == NULL) //检查是不是在双链表中的位置
102 printf("位置不合法。\n");
103 else if(p->next == NULL) //最后一个结点特殊处理，原因最后一个结点p->next没有prior
104 {
105 p->prior->next = NULL;
106 free(p);
107 }
108 else //进行删除操作
109 {
110 p->prior->next = p->next;
111 p->next->prior = p->prior;
112 free(p);
113 }
114 }
115
116 ///////////////////////////////////////////
117 int main()
118 {
119 DLinkList list,start;
120 list = DLinkListCreatT();
121 for(start = list->next; start != NULL; start = start->next)
122 printf("%d ",start->data);
123 printf("\n");
124 int i;
125 ElemType x;
126 printf("请输入要查找元素的值：");
127 scanf("%d",&x);
128 i = DLinkListFind(list,x);
129 if(i)
130 printf("在链表中的位置为：%d\n",i);
131 else
132 printf("没有这个元素。\n");
133 printf("请输入插入位置：");
134 scanf("%d",&i);
135 printf("请输入插入元素的值：");
136 scanf("%d",&x);
137 DLinkListInsert(list,i,x);
138 for(start = list->next; start != NULL; start = start->next)
139 printf("%d ",start->data);
140 printf("\n");
141 printf("请输入要删除的位置：");
142 scanf("%d",&i);
143 DLinkListDelete(list,i);
144 for(start = list->next; start != NULL; start = start->next)
145 printf("%d ",start->data);
146 printf("\n");
147
148 return 0;
149 }
|
