数据结构第五天

一、双向链表

1、单链表构成的循环链表
最后一个结点本来指向NULL，改为指向头结点或者第一个结点。
实现方法，将原来指向NULL的地方改成指向ls->head，或者ls->head->next。
While()循环的条件改为！= ls->head或者ls->head->next。

#include "Linklist.h"
#include <stdlib.h>
#include <stdio.h>

List *Creat()
{	
	List *ls = (List *)malloc(sizeof(List)/sizeof(char));
	if(NULL == ls)
		return NULL;
	
	ls->head = (Node *)malloc(sizeof(Node)/sizeof(char));
	if(NULL == ls->head)
	{
		free(ls);
		return NULL;
	}
	
	ls->head->next = NULL;
	ls->head->pre  = NULL;
	return ls;
}

//头插
BOOL inster_head(List *ls,Data data)
{
	if(NULL == ls)
		return ERROR;
	
	Node *pa = (Node *)malloc(sizeof(Node)/sizeof(char));
	
	if(NULL == pa)
		return ERROR;
	
	pa->data = data;
	pa->next = ls->head->next;
	pa->pre  = ls->head;
	ls->head->next = pa;
	if(pa->next != NULL)
		pa->next->pre  = pa; 

	return TRUE;
}

//尾插
BOOL inster_last(List *ls,Data data)
{
	if(NULL == ls)
		return ERROR;
	
	Node *pa = (Node *)malloc(sizeof(Node)/sizeof(char));
	
	if(NULL == pa)
		return ERROR;
	
	pa->data = data;
	pa->next = NULL;
	
	Node *tmp = ls->head;
	while(tmp->next)
	{
		tmp = tmp->next;
	}
	tmp->next = pa;
	pa->pre   = tmp;
	
	return TRUE;
}

//链表按位置插
BOOL inster_pos(List *ls,int index,Data data)
{
	if(NULL == ls || index < 1)
		return ERROR;
	
	Node *pa = (Node *)malloc(sizeof(Node)/sizeof(char));
	if(NULL == pa)
		return ERROR;
	
	Node *tmp = ls->head;
	int i;
	for(i = 0; i < index-1; i++)
	{
		tmp = tmp->next;
		if(tmp == NULL)
		{
			printf("链表越界，长度=%d\n",index);
			return ERROR;
		}
	}
	
	pa->data = data;		//要插入的数据
	pa->next = tmp->next;	
	pa->pre  = tmp;
	tmp->next = pa;	
	if(pa->next != NULL)	
	pa->next->pre = pa;
	
	return TRUE;
}

//删除数据（按位置）
BOOL delete_index(List *ls,int index)
{
	if(NULL == ls)
		return;
	
	Node *tmp = ls->head;
	int i;
	for(i = 0; i < index-1; i++)
	{
		tmp = tmp->next;
		if(NULL =&
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