首页 » Program » C/C++ » 正文

Two-way linked-list

双向链表在链表的基础上新增了指向前一个结点的指针prior, 由于链表没设表长属性,我在程序用了count变量记录表长以方便插入操作。这里我实现的是双向链表的创建,打印,插入和删除操作。

#include <stdio.h>
 2 #include <malloc.h>
 3
 4 typedef struct shuang
 5 {
 6     struct shuang *prior;          //指向前一个结点
 7     int data;
 8     struct shuang *next;           //指向后一个结点
 9 } snode, *slinklist;
10
11 //打印双向链表元素
12 void print_shuang(slinklist L)
13 {
14     slinklist p;
15     p = L->next;
16     while (p!=NULL)
17         {
18             printf("%d ",p->data);
19             p = p->next;
20         }
21     printf("\n");
22 }
23
24 //创建双向链表
25 void creat_shuang(slinklist L)   //得结点地址
26 {
27     slinklist p,q;
28     L->next = NULL;              //头结点的后指针先指向null
29     printf("请输入链表元素\n");
30     q = (snode *)malloc(sizeof(snode));
31     scanf("%d",&(q->data));
32     q->next = L->next;           //NULL给了q->next
33     L->next = q;                 //L(头结点)指向新的q
34     q->prior = L;                //新的q的前指针指向前一个L
35     p = (snode *)malloc(sizeof(snode));
36     while (scanf("%d",&(p->data))!=EOF)
37         {
38             p->next = q->next;       //p的后指针指向q的后指针
39             q->next = p;             //q的后指针改为指向新的p
40             p->prior = q;            //新的p的前指针指向上一个q
41             q = p;                   //上一个q变成这次新的p(q记录p)
42             p = (snode *)malloc(sizeof(snode));   //p再新开
43         }
44 }
45
46 //插入
47 int ins(slinklist L,int i,int e)
48 {
49     slinklist p,q,s;
50     int j = 1;
51     int count = 0;               //(无奈新增count来记录)
52     p = L;
53     s = (slinklist)malloc(sizeof(slinklist));
54     s->data = e;
55     while (p->next)
56         {
57             p = p->next;           //移动到表尾结点(最后一个结点)
58             count++;               //记录双向链表长度,方便在表尾插入结点
59         }
60     if (i==count+1)      //1.插入表尾
61         {
62             p->next = s;       //p的后指针指向s
63             s->next = NULL;    //s的后指针指向空
64             s->prior = p;     //s的前指针指向p
65             return 1;
66         }
67     else
68         {
69             p = L->next;            //移动到第一个结点
70             while (p&&j<i)
71                 {
72                     q = p;            //q记录前一个结点,方便后续插入
73                     p = p->next;
74                     j++;
75                 }
76             if (j==1)        //2.插入表前(头结点后)
77                 {
78                     L->next->prior = s;
79                     s->next = L->next;
80                     s->prior = L;
81                     L->next = s;
82                     return 1;
83                 }
84             p->prior = s;       //3.插入结点间
85             s->next = q->next;
86             s->prior = q;
87             q->next = s;
88             return 1;
89         }
90 }
91
92 //删除
93 int del(slinklist L,int i)
94 {
95     slinklist p;
96     int j = 1;
97     p = L->next;
98     while (p&&j<i)
99         {
100             p = p->next;
101             j++;
102         }
103     if (p->next==NULL)       //1.删除最后一个结点
104         {
105             p->prior->next = NULL;        //p的前指针的后指针直接空就ok
106             free(p);
107             return 1;
108         }
109     p->prior->next = p->next;     //2.删除结点在结点间或第一个结点(头结点后的那个结点)
110     p->next->prior = p->prior;
111     free(p);
112     return 1;
113 }
114
115
116 int main()
117 {
118     slinklist L;         //记得L是指针(地址)!
119     int i,e;
120     int a;
121     L = (snode *)malloc(sizeof(snode));
122     creat_shuang(L);
123     printf("建立的双向链表为:\n");
124     print_shuang(L);
125     //双向链表创建完毕--------------------------
126     printf("请输入要插入元素的位置:\n");
127     scanf("%d",&i);
128     printf("请输入要插入元素值:\n");
129     scanf("%d",&e);
130     if (ins(L,i,e)!=1)
131         {
132             printf("插入失败!\n");
133             return 0;
134         }
135     //双向链表插入完毕--------------------------
136     print_shuang(L);
137     printf("请输入你要删除的元素的位置:\n");
138     scanf("%d",&a);
139     if (del(L,a)!=1)
140         {
141             printf("删除失败!\n");
142             return 0;
143         }
144     //双向链表删除完毕-------------------------
145     print_shuang(L);
146     return 0;
147 }

赞 (0)

Comment

please input captcha *