单链表-C语言

001	////////////////////////////////////////////

002	//单链表的初始化，建立，插入，查找，删除。//

003	//Author:Wang Yong                        //

004	//Date: 2010.8.19                         //

005	////////////////////////////////////////////

006

007

008

#include

009

#include

010

011	typedef int ElemType;

012	////////////////////////////////////////////

013

014

//定义结点类型

015	typedef struct Node

016

{

017	ElemType data;              //单链表中的数据域

018	struct Node *next;          //单链表的指针域

019	}Node,*LinkedList;

020

021	////////////////////////////////////////////

022

023

//单链表的初始化

024

025	LinkedList LinkedListInit()

026

{

027

Node *L;

028	L = (Node *)malloc(sizeof(Node));   //申请结点空间

029	if(L == NULL)                       //判断是否有足够的内存空间

030	printf("申请内存空间失败 ");

031	L->next = NULL;                  //将next设置为NULL,初始长度为0的单链表

032

}

033

034	////////////////////////////////////////////

035

036	//单链表的建立1，头插法建立单链表

037

038	LinkedList LinkedListCreatH()

039

{

040

Node *L;

041	L = (Node *)malloc(sizeof(Node));   //申请头结点空间

042	L->next = NULL;                      //初始化一个空链表

043

044	ElemType x;                         //x为链表数据域中的数据

045	while(scanf("%d",&x) != EOF)

046

{

047

Node *p;

048	p = (Node *)malloc(sizeof(Node));   //申请新的结点

049	p->data = x;                     //结点数据域赋值

050	p->next = L->next;                    //将结点插入到表头L-->|2|-->|1|-->NULL

051	L->next = p;

052

}

053

return L;

054

}

055

056	////////////////////////////////////////////

057

058	//单链表的建立2，尾插法建立单链表

059

060	LinkedList LinkedListCreatT()

061

{

062

Node *L;

063	L = (Node *)malloc(sizeof(Node));   //申请头结点空间

064	L->next = NULL;                  //初始化一个空链表

065

Node *r;

066	r = L;                          //r始终指向终端结点，开始时指向头结点

067	ElemType x;                         //x为链表数据域中的数据

068	while(scanf("%d",&x) != EOF)

069

{

070

Node *p;

071	p = (Node *)malloc(sizeof(Node));   //申请新的结点

072	p->data = x;                     //结点数据域赋值

073	r->next = p;                 //将结点插入到表头L-->|1|-->|2|-->NULL

074

r = p;

075

}

076	r->next = NULL;

077

078

return L;

079

}

080

081	////////////////////////////////////////////

082

083	//单链表的插入，在链表的第i个位置插入x的元素

084

085	LinkedList LinkedListInsert(LinkedList L,int i,ElemType x)

086

{

087	Node *pre;                      //pre为前驱结点

088

pre = L;

089	int tempi = 0;

090	for (tempi = 1; tempi < i; tempi++)

091	pre = pre->next;                 //查找第i个位置的前驱结点

092	Node *p;                                //插入的结点为p

093	p = (Node *)malloc(sizeof(Node));

094	p->data = x;

095	p->next = pre->next;

096	pre->next = p;

097

098

return L;

099

}

100

101	////////////////////////////////////////////

102

103	//单链表的删除，在链表中删除值为x的元素

104

105	LinkedList LinkedListDelete(LinkedList L,ElemType x)

106

{

107	Node *p,*pre;                   //pre为前驱结点，p为查找的结点。

108	p = L->next;

109	while(p->data != x)              //查找值为x的元素

110

{

111

pre = p;

112	p = p->next;

113

}

114	pre->next = p->next;          //删除操作，将其前驱next指向其后继。

115

free(p);

116

return L;

117

}

118

119	/////////////////////////////////////////////

120

121	int main()

122

{

123	LinkedList list,start;

124	/*  printf("请输入单链表的数据：");

125	list = LinkedListCreatH();

126	for(start = list->next; start != NULL; start = start->next)

127	printf("%d ",start->data);

128	printf(" ");

129	*/  printf("请输入单链表的数据：");

130	list = LinkedListCreatT();

131	for(start = list->next; start != NULL; start = start->next)

132	printf("%d ",start->data);

133	printf(" ");

134

135

int i;

136	ElemType x;

137	printf("请输入插入数据的位置：");

138	scanf("%d",&i);

139	printf("请输入插入数据的值：");

140	scanf("%d",&x);

141	LinkedListInsert(list,i,x);

142	for(start = list->next; start != NULL; start = start->next)

143	printf("%d ",start->data);

144	printf(" ");

145	printf("请输入要删除的元素的值：");

146	scanf("%d",&x);

147	LinkedListDelete(list,x);

148	for(start = list->next; start != NULL; start = start->next)

149	printf("%d ",start->data);

150	printf(" ");

151

152

return 0;

153

}