数据结构-第三次实验_从键盘输入一系列整数(不少于3个整数),存储在单链表中。要求在创建单链表时,按照

实验2 顺序表的运用

一、实验目的
1、掌握使用头插法、尾插法建立单链表的基本方法。
2、掌握单链表的插入、删除算法的实现，并能灵活运用

二、实验内容
用单链表实现存储数据并处理数据。具体要求如下：
1.利用教材中定义单链表的方存储整型数据（单链表的定义如下），要求使用头文件实现单链表的以下操作，要求使用带头结点的单链表。
typedef int ElemType;
typedef struct sNode{
ElemType data;
struct sNode * next;
}LinkedList, *LinkList;
① 初始化单链表 LinkList ListInitialize() :
返回初始化以后单链表的头指针
② 求单链表的长度 int ListLength (LinkedList * head)
③ 单链表的插入操int ListInsert(LinkedList *head, int i, ElemType x)
④ 单链表的删除操作 int ListDelete(LinkedList *head, int i,ElemType *x)
⑤ 取数据元素 int ListGet(LinkedList *head, int i,ElemType *x)
⑥数据元素遍历打印 void Display(LinkedList *head)
⑦ 完成单链表的数据元素就地逆置void Reverse(LinkedList *head)
⑧ 获取单链表链尾指针 LinkedList * GetTail(LinkedList *head)
⑨ 释放单链表操作 void Destroy(LinkedList ** head)
具体功能要求如下：
第一步：从键盘依次输入以下数据并采用尾插法插入单链表
28 19 35 28 56 10 16 56 56 90 73 82 82 56
第二步：删除其中的重复数据元素
第三步：实现单链表中的数据就地逆置。
注意每步操作之后显示链表的内容。

//LinkedList.h
#include "malloc.h"
#include <stdio.h>
typedef int Elemtype;
typedef struct Node {
	Elemtype data;
	struct Node * next;
}LinkedList, *LinkList;
//初始化链表方法1
void LinkedListIntialize(LinkedList **head) {
	*head = (LinkedList*)malloc(sizeof(struct Node));
	(*head)->next = NULL;
}
//初始化链表方法2
LinkedList * ListIntialize() {
	LinkedList * head;
	head = (LinkedList*)malloc(sizeof(struct Node));
	head->next = NULL;
	return head;
}
//返回链表长度
int ListLength(LinkList head) {
	int size = 0;
	LinkList p = head;
	while (p->next != NULL) {
		p = p->next;
		size++;
	}
	return size;
}

LinkList getTail(LinkList head) {                      //得到尾指针 
	LinkList p;
	p = head;
	while (p->next != NULL) {
		p = p->next;
	}
	return p;
}

int LinkListInsertTail(LinkList head, Elemtype x) {     //尾插 
	LinkList tail;
	LinkList q;
	tail = getTail(head);
	q =(LinkedList*) malloc(sizeof(LinkedList));
	q->data = x;
	q->next = NULL;
	tail->next = q;
	return 1;
}

int LinkListInsert(LinkList head, int i, Elemtype x) {          //插入 
	LinkedList *p, *q;
	int j;
	p = head;
	j = -1;
	while (p->next != NULL && j < i - 1) {
		p = p->next;
		j++;
	}
	//循环结束时，p指针定位于插入位置之前的结点
	q = (LinkedList*)malloc(sizeof(LinkedList));
	q->data = x;
	q->next = p->next;
	p->next = q;
	return 1;
}
//有序插入方法
int ListInsertSorted(LinkList head, Elemtype x) {
	LinkList pre, curr,q;
	pre = head;
	curr = head->next;
	while (curr != NULL && curr->data <= x  ) {
		pre = curr;
		curr = curr->next;
	}
	//滑动指针，直到curr指向的结点数据域的值大于x，或者curr等于链表尾结点的指针域NULL
	q = (LinkList)malloc(sizeof(LinkedList));
	q->data = x;
	q->next = curr;
	pre->next = q;
	return 1;
}

int LinkedListDelete(LinkList head, int i, Elemtype *x) {            //删除 
	LinkList p,s;
	int j = -1;
	p = head;
	while (p->next != NULL && p->next->next!=NULL && j < i - 1) {
		p = p->next;
		j++;
	}
	//循环结束时，p指针指向的是被删除结点的前一个结点
	if (j!=i-1 || p->next == NULL) {
		printf("删除位置不合法\n");
		return 0;
	}
	s = p->next;
	*x = s->data;
	p->next = s->next;
	free(s);
	return 1;
}

void Destroy(LinkList* head) {               //销毁链表 
	LinkList p1, p;
	p =(*head);
	while (p != NULL) {
		p1 = p;
		p = p->next;
		free(p1);
	}
	(*head) = NULL;
}

void printLinkList(LinkedList* head) {         //打印链表 
	LinkedList *p;
	p = head->next;
	while (p) {
		printf("%d\t", p->data);
		p = p->next;
	}
	printf("\n");
}

void ListRepDelete(LinkedList *L)         //删除重复元素 
{
 	LinkedList *p,*q;
 	p = L->next;
 	while(p!=NULL)
 	{
 		q = p;
 		while(q->next!=NULL)
 		{
 			if(p->data==q->next->data)//删除q这个节点 
 			{
 				q->next = q->next->next;//删除q->next这个节点 
			}
			else
			{
				q = q->next;
			} 
		 }
		 p = p->next;
	}
 } 
 
void reverse(LinkedList *head)          //原地逆置 
{
	LinkedList *p,*q;
	p = head->next;
	head->next = NULL;
	while(p)
	{
		q = p;
		p = p->next;
		q->next = head->next;
		head->next = q;
	}
 } 
 
LinkedList.c
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include "LinkedList.h"

int main()
{
	LinkedList *head;
	int i;
	int x;
	printf("请输入要插入的数据，末尾要输入Enter + Ctrl + Z + Enter来结束输入\n");
	LinkedListIntialize(&head);
	while(scanf("%d",&x)!= EOF)
	{
		LinkListInsertTail(head,x);
	}
	printf("插入的数据：\n"); 
	printLinkList(head);
	printf("\n");
	printf("将重复的数据删除:\n");
    ListRepDelete(head);
	printLinkList(head);
	printf("\n");
	printf("将数据原地逆置:\n");
	reverse(head);
	printLinkList(head);
	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
185
186
187
188
189
190