数据结构 C 代码 2.3: 双向链表_数据结构c语言版2.3按例代码

摘要: 双向链表比单链表稍复杂, 也更不常用. 主要是为了练习链表的变种, 寻找更多设计的感觉. 这样在面对实际问题的时候, 就具有一定的建模能力.

1. 代码

#include <stdio.h>
#include <malloc.h>

/**
 * Double linked list of integers. The key is char.
 */
typedef struct DoubleLinkedNode{
	char data;
	struct DoubleLinkedNode *previous;
	struct DoubleLinkedNode *next;
} DLNode, *DLNodePtr;

/**
 * Initialize the list with a header.
 * @return The pointer to the header.
 */
DLNodePtr initLinkList(){
	DLNodePtr tempHeader = (DLNodePtr)malloc(sizeof(struct DoubleLinkedNode));
	tempHeader->data = '\0';
	tempHeader->previous = NULL;
	tempHeader->next = NULL;
	return tempHeader;
}// Of initLinkList

/**
 * Print the list.
 * @param paraHeader The header of the list.
 */
void printList(DLNodePtr paraHeader){
	DLNodePtr p = paraHeader->next;
	while (p != NULL) {
		printf("%c", p->data);
		p = p->next;
	}// Of while
	printf("\r\n");
}// Of printList

/**
 * Insert an element to the given position.
 * @param paraHeader The header of the list.
 * @param paraChar The given char.
 * @param paraPosition The given position.
 */
void insertElement(DLNodePtr paraHeader, char paraChar, int paraPosition){
	DLNodePtr p, q, r;

	// Step 1. Search to the position.
	p = paraHeader;
	for (int i = 0; i < paraPosition; i ++) {
		p = p->next;
		if (p == NULL) {
			printf("The position %d is beyond the scope of the list.", paraPosition);
			return;
		}// Of if
	} // Of for i

	// Step 2. Construct a new node.
	q = (DLNodePtr)malloc(sizeof(struct DoubleLinkedNode));
	q->data = paraChar;

	// Step 3. Now link.
	r = p->next;
	q->next = p->next;
	q->previous = p;
	p->next = q;
	if (r != NULL) {
		r->previous = q;
	}// Of if
}// Of insertElement

/**
 * Delete an element from the list.
 * @param paraHeader The header of the list.
 * @param paraChar The given char.
 */
void deleteElement(DLNodePtr paraHeader, char paraChar){
	DLNodePtr p, q, r;
	p = paraHeader;

	// Step 1. Locate.
	while ((p->next != NULL) && (p->next->data != paraChar)){
		p = p->next;
	}// Of while

	// Step 2. Error check.
	if (p->next == NULL) {
		printf("The char '%c' does not exist.\r\n", paraChar);
		return;
	}// Of if

	// Step 3. Change links.
	q = p->next;
	r = q->next;
	p->next = r;
	if (r != NULL) {
		r->previous = p;
	}// Of if

	// Step 4. Free the space.
	free(q);
}// Of deleteElement

/**
 * Unit test.
 */
void insertDeleteTest(){
	// Step 1. Initialize an empty list.
	DLNodePtr tempList = initLinkList();
	printList(tempList);

	// Step 2. Add some characters.
	insertElement(tempList, 'H', 0);
	insertElement(tempList, 'e', 1);
	insertElement(tempList, 'l', 2);
	insertElement(tempList, 'l', 3);
	insertElement(tempList, 'o', 4);
	insertElement(tempList, '!', 5);
	printList(tempList);

	// Step 3. Delete some characters (the first occurrence).
	deleteElement(tempList, 'e');
	deleteElement(tempList, 'a');
	deleteElement(tempList, 'o');
	printList(tempList);

	// Step 4. Insert to a given position.
	insertElement(tempList, 'o', 1);
	printList(tempList);
}// Of appendInsertDeleteTest

/**
 * Address test: beyond the book.
 */
void basicAddressTest(){
	DLNode tempNode1, tempNode2;

	tempNode1.data = 4;
	tempNode1.next = NULL;

	tempNode2.data = 6;
	tempNode2.next = NULL;

	printf("The first node: %d, %d, %d\r\n",
		&tempNode1, &tempNode1.data, &tempNode1.next);
	printf("The second node: %d, %d, %d\r\n",
		&tempNode2, &tempNode2.data, &tempNode2.next);

	tempNode1.next = &tempNode2;
}// Of basicAddressTest

/**
 * The entrance.
 */
void main(){
	insertDeleteTest();
	basicAddressTest();
}// Of main
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157

2. 运行结果

Hello!
The char 'a' does not exist.
Hll!
Holl!
The first node: 1703632, 1703632, 1703640
The second node: 1703620, 1703620, 1703628
Press any key to continue
1
2
3
4
5
6
7

3. 代码说明

1. 仅实现了打印、插入、删除.
2. 每个相关指针都要改, 必须画个图来辅助写程序.
3. 尾结点删除时需要注意. 需要进行边界测试.

4. 作业

1. 抄代码.
2. 进行 insertElement 等函数进一步的测试.
3. 自己实现 locateElement 函数.
4. 挑本贴 bug 并留言.
5. 写 CSDN 博客. 必须有图示, 可以用工具画, 或者手绘拍照.

附一. 2021 级代码

麦尔哈巴·阿卜杜拉同学的代码, 注释写得详细.

#include<bits/stdc++.h>
using namespace std;
typedef int Status;
typedef int ElemType;
#define OVERFLOW -1
#define ERROR 0
#define OK 1

//-----双向链表的储存结构-----
typedef struct DuLNode
{
    ElemType data;
    struct DuLNode *prior;
    struct DuLNode *next;
} DuLNode, *DuLinkList;

DuLinkList L;

//1、双向链表初始化
Status InitList_DuL(DuLinkList &L)
{
    //构造一个空的双向链表L
    L = new DuLNode;
    L->prior = NULL;
    L->next = NULL;
    return OK;
}

//2、双向链表按位查找
DuLNode *GetElem_DuL(DuLinkList L, int i)
{
    DuLNode *p = L->next;
    int j = 1;
    while(p && j < i)
    {
        p = p->next;
        j++;
    }
    if(!p || j > i)
        return NULL;
    else
        return p;
}

//3、双向链表前驱
Status PriorElem_DuL(DuLinkList L, ElemType cur_e, ElemType &pre_e)
{
    DuLNode *p;
    if(!(p = LocateElem_DuL(L, cur_e)))                //在L中确定第i个元素的位置指针p
        return ERROR;
    pre_e = p->prior->data;
    return OK;
}

//4、双向链表后继
Status NextElem_DuL(DuLinkList L, ElemType cur_e, ElemType &next_e)
{
    DuLNode *p;
    if(!(p = LocateElem_DuL(L, cur_e)))                //在L中确定第i个元素的位置指针p
        return ERROR;
    next_e = p->next->data;
    return OK;
}

//5、双向链表插入
Status ListInsert_DuL(DuLinkList &L, int i, ElemType e)
{
    //在带头结点的双向链表L中第i个位置之前插入元素e
    DuLNode *p;
    if(!(p = GetElem_DuL(L, i)))
        return ERROR;
    DuLNode *s = new DuLNode;
    s->data = e;
    s->prior = p->prior;
    p->prior->next = s;
    s->next = p;
    p->prior = s;
    return OK;
}

//11、双向链表删除
Status ListDelete_DuL(DuLinkList &L, int i)
{
    //删除带头结点的双向链表L中的第i个元素
    DuLNode *p;
    if(!(p = GetElem_DuL(L, i)))
        return ERROR;
    p->prior->next = p->next;
    p->next->prior = p->prior;
    delete p;
    return OK;
}

int main()
{
    cout<<"------------------------双向链表菜单----------------------"<<'\n';
    cout<<"操作0：退出程序"<<'\n';
    cout<<"操作1：创建一个带头结点的双向链表，且遍历此链表"<<'\n';
    cout<<"操作2：在双向链表中的第i个结点前插入一个结点值为e的正整数"<<'\n';
    cout<<"操作3：删除双向链表链表中的第j个结点"<<'\n';
    int a, n, flag = 1;
    while(flag)
    {
        cout<<'\n'<<"请选择要执行的操作：";
        while(cin>>a)
        {
            if(a < 0 || a > 5)
                cout<<"请选择正确操作编号：";
            else
                break;
        }
        switch(a)
        {
        case 0:
        {
            cout<<"感谢使用本程序，祝您生活愉快！"<<'\n';
            flag = 0;
            break;
        }
        case 1:
        {
            cout<<"----菜单-----"<<'\n';
            cout<<"操作1：前插法"<<'\n';
            cout<<"操作2：后插法"<<'\n';
            cout<<"-------------"<<'\n';
            cout<<"请选择单链表的创建方式：";
            int b;
            while(cin>>b)
            {
                if(b != 1 && b != 2)
                    cout<<"请选择正确操作编号：";
                else
                    break;
            }
            cout<<"请输入要建立的单链表的元素个数：";
            cin>>n;
            if(b == 1)
            {
                cout<<"请按逆位序依次输入这"<<n<<"个元素：";
                CreateList_H_DuL(L, n);
            }
            else if(b == 2)
            {
                cout<<"请按正位序依次输入这"<<n<<"个元素：";
                CreateList_R_DuL(L, n);
            }
            cout<<"单链表创建完毕：";
            TraverseList_DuL(L);
            break;
        }
        case 2:
        {
            int i;
            ElemType e;
            cout<<"在单链表中的第i个结点前插入一个结点值为e的正整数，请依次输入i和e的值：";
            cin>>i>>e;
            if(ListInsert_DuL(L, i, e))
            {
                cout<<"单链表插入完毕：";
                TraverseList_DuL(L);
            }
            else
                cout<<"i值不合法！"<<'\n';
            break;
        }
        case 3:
        {
            int j;
            cout<<"删除单链表中的第j个结点，请输入j的值：";
            cin>>j;
            if(ListDelete_DuL(L, j))
            {
                cout<<"单链表删除完毕：";
                TraverseList_DuL(L);
            }
            else
                cout<<"j值不合法！"<<'\n';
            break;
        }
        }
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184