链式线性表的基本操作_8579 链式线性表的基本操作

实验目的：

掌握线性表的链式存储结构

熟练掌握链式线性表的基本操作：创建、查找、取值、插入、删除等算法。

实验要求：

利用链式结构实现线性表的基本操作，并利用这些操作完成下面的任务。

实验任务：

1．创建一个链表，表中元素依次为：s、t、d、i、o（均为char类型）；

2．查找链表中是否包含’b’字符；

3．从链表中取出第3个元素并返回其值；

4．在第3个元素后面插入3个新的元素依次为：l、i、b；

5．将链表中的最后两个元素删除；

6．将链表中的元素全部输出。

实验内容

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

#define OK 1
#define ERROR 0

typedef int Status;
typedef char ElemType;

//定义线性表的储存结构
typedef struct LNode {
    ElemType data;
    struct LNode *next;
} LNode, *LinkList;

//初始化链表 
Status InitLinkList(LinkList *L) {
    *L = (LinkList) malloc(sizeof(LNode));
    (*L)->next = NULL;
    return OK;
}

//尾插入构建单链表
void CreatLinkList(LinkList *L, int n) {
    LinkList p, q;
    p = *L;
    for (int i = 0; i < n; i++) {
        printf("请输入链表的第%d个元素：", i);
        q = (LinkList)malloc(sizeof(LNode));//创建新的节点，
        scanf("%s", &q->data);
        p->next = q;
        p = q;
    }
    p->next = NULL;
}
/*单链表表长*/
Status LengthList(LinkList *L) {
    int i = 0;
    LinkList p, q;
    p = *L;
    if (p->next == NULL) return ERROR;
    while (p->next != NULL) {
        i++;
        p = p->next;
    }
    return i;
}

//单链表输出函数
void Display(LinkList *L) {
    LNode *p;
    p = (*L)->next;
    while (p) {
        printf("%c ", p->data);
        p = p->next;
    }
    printf("\n");
}

//取值，按位置查找，找到值 
Status GetLinkList(LinkList *L,int i,ElemType *e) {
	int j=1;
	LinkList p,q;
	p = *L;
	if(i<1||!p->next||i>LengthList(L)) {
		return ERROR;
	}
	while(j<=i&&p){
		p=p->next;
		j++;
	}
	if(j-1==i) {
		*e=p->data;
		return OK;	
	}else{
		return ERROR;
	}  
}

//取值，按照值查找，找到所在位置 
Status LocateLinklist(LinkList *L, ElemType e) {
    int i = 1;
    LinkList p, q;
    p = (*L)->next;
    while (p->data != e && p->next) {
        p = p->next;
        i++;
    }
    if (p->data != e) return -1;
    else return i;
}

//在i个位置后插入e，若成功则返回1，若失败则返回0
Status InsertLinkList(LinkList *L, int i, ElemType e) {
    int j = 1;
    LinkList p, q;
    p = *L;
    if (i < 1 || !p->next || i > LengthList(L))    //插入位置不合理
    {
        return ERROR;
    }
    while (p && j <= i)                     //找到插入点
    {
        p = p->next;
        j++;
    }
    q = (LinkList) malloc(sizeof(LNode));//创建插入新节点
    q->data = e;
    q->next = p->next;
    p->next = q;
    return OK;
}

//删除指定位置的元素，，删除成功返回1，失败返回0
Status DeleteLinkList(LinkList *L, int i) {
    int j = 1;
    LinkList p, q;
    p = *L;
    if (i < 1 || !p->next || i > LengthList(L)) {
        return ERROR;
    }
    while (j < i && p->next) {
        p = p->next;
        j++;
    }
    q = p->next;
    p->next = q->next;
    free(q);
    return OK;
}

int main(){
	LinkList list;
	InitLinkList(&list);
	CreatLinkList(&list,5);
	Display(&list);
	//按照值查找
	int local=LocateLinklist(&list,'b');
	if(local>0){
		printf("字符b的位置是：%d\n",local);
	}else {
		printf("字符b不在该链表中\n");
	}
	//按位置查找 
	char c1;
	GetLinkList(&list,3,&c1);
	printf("第三个字符是：%c\n", c1);
	//插入三个元素:l,i,b 
	InsertLinkList(&list,3,'l');
	InsertLinkList(&list,4,'i');
	InsertLinkList(&list,5,'b');
	printf("插入三个元素之后的链表：");
	Display(&list);
	//删除最后两个元素
	DeleteLinkList(&list,LengthList(&list));
	DeleteLinkList(&list,LengthList(&list));
	printf("删除最后两个元素之后的链表：");
	Display(&list);
	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

运行结果：