数据结构与算法

数据结构与算法(一)-单向链表

大话数据结构笔记， 线性表链式存储，元素的插入，获取，表的初始化，删除，销毁

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
#define ERROR 0
#define OK 1

typedef int ElemType;
typedef struct Node {
    ElemType data;
    Node *next;	
} Node;

typedef struct Node *LinkList;

typedef int Status;

//初始化size个长度的单链表
LinkList InitLinkList(int size)
{
	//头节点
	LinkList pHead;
	pHead = (LinkList)malloc(sizeof(Node));
	if(NULL == pHead) {
		printf("内存分配失败 \n");
		exit(0);
	}
	pHead->data = 0;
	pHead->next = NULL;
	
	int i;
	LinkList q, pTail;
	pTail = pHead;
	for(i=1; i<size; i++) {
		q = (LinkList)malloc(sizeof(Node));
		if(NULL == q) {
			printf("内存分配失败\n");
			exit(0);
		}
		q->next = NULL;
		q->data = NULL;
		pTail->next = q;
		pTail = q;
	}
	return pHead;
}

//线性表的链式存储结构
//用e返回单链表中第 i 个元素的值
Status GetLinkListElem(LinkList L, int i, ElemType *e)
{
	int j = 1;
	LinkList p; //声明一个节点
	p = L->next; //指向单链表的第一个节点
	while(p || j<i){
		p = p->next;
		++j;
	}

	if(!p || j>i) {//!p 已到达链表的结尾 j>i 第j个元素超过了 i
		return ERROR;
	}

	*e = p->data;
	return OK;
}

//在单链表L中的第i个位置插入元素 e， 单链表长度加 1 
Status InsertLinkList(LinkList *L, int i, ElemType e)
{
	int j;
	j = 1;
	LinkList p, s;
	p = *L;
	while(p || j < i) {
		++j;
		p = p->next;
	}

	if(!p || j > i) {
		return ERROR;
	}

	s = (LinkList)malloc(sizeof(Node));x
	s->data = e;
	s->next = p->next; //将p的后继节点赋值为s的后继节点
	p->next = s;
	return OK;
}


//打印单链表-不打印头节点值
void PrintLinkList(LinkList list)
{
	LinkList pt;
	pt = list->next;//头结点的下一个节点
	while(!pt) {
		printf("%d\n", pt->next);
		pt = pt->next;
	}
	putchar("\n");
}

//销毁整过单链表
void DestroyLinkList(LinkList *L)
{
	Node node = null;
	while(*L != NULL) {
		node = (*L)->next;//当前节点的下一个节点
		free(*L); 		//释放当前节点
		*L = node; 		//把下一个节点赋值给 *L，进行下到下一次循环
	}
}