Two-way linked-list | LSABLOG

首页 » 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