上一节学完了单链表的基本操作,这里再像顺序表一样跑一下代码。毕竟只靠看是记不住多少东西的。
单链表结构
typedef int ElemType;
typedef struct LNode {
ElemType data;
struct LNode *next;
} LNode, *LinkList;
// 遍历输出单链表
void PrintLists(LinkList L) {
LNode * p = L->next; // LinkList p 也是可以的
while (p) {
printf("%d", p->data);
p = p->next;
printf("\r\n");
}
}
创建
单链表创建有两种模式,尾插法和头插法,具体概念在上一节已经写了。
头插法
LinkList CreatList(LinkList L) {
int x;
LNode *s; //辅助指针
L = (LinkList) malloc(sizeof(LNode)); //创建头结点
L->next = NULL; //初始为空表
scanf("%d", &x); // 读取标准输入
while (x != 999) { //输入999表示结束
s = (LNode *) malloc(sizeof(LNode)); // 申请一个空间,强制类型转换
s->data = x; //对新结点的数据域赋值
s->next = L->next; //新节点的后继指向第一个结点
L->next = s; //头结点的后继指向新结点
scanf("%d", &x); //读取标准输入
}
return L;
}
在main 方法中初始化并调用:
LinkList L;
LinkList search;
L = CreatList(L); // 输入数据为 2 3 4 999
PrintLists(L);
/*运行结果
5
4
3
2
*/
尾插法 L = CreatList2(L);
LinkList creatList2(LinkList L) {
int x;
L = (LinkList) malloc(sizeof(LNode));
LNode *s, *r = L; // r为表尾指针,指向表尾
scanf("%d", &x);
while (x != 999) {
s = (LNode *) malloc(sizeof(LNode));
s->data = x;
s->next = L->next;
r->next = s;
r = s;
scanf("%d", &x);
}
r->next = NULL;
return L;
}
/*
2
3
4
5
*/
插入InsertElem(L, 2, 90)
LNode *InsertElem(LinkList L, int i, ElemType x) {
LNode * p = GetElem(L, i - 1);
LinkList s = (LNode *) malloc(sizeof(LNode));
s->next = p->next;
s->data = x;
p->next = s;
}
/*
5
90
4
3
2
*/
按序号查找 search = GetElem(L, 2)
LNode *GetElem(LinkList L, int i) {
int j = 1; // 计数 从1开始
LNode * p = L->next; // 第一个节点指针赋予 p a1
if (i == 0) return L; // 若 i = 0 ,返回头结点
if (i < 1) return NULL; // i 无效,返回 null
while (p && j < i) { // 从第一个结点开始查找,直到 i
p = p->next; // 下一个结点指针
j++;
}
if (j == i) {
return p;
} else {
return NULL;
}
}
/*
按序号查找成功
4
*/
按值查找 LNode(L,2)
LNode *LocateElem(LinkList L, ElemType e) {
LNode * p = L->next;
while (p != NULL && p->data != e) { // 从第一个结点开始查找 data 域为 e 的结点
p = p->next;
}
return p;
}
/*
按值查找成功
2
*/
删除 DeleElem(L, 2)
LNode *DeleElem(LinkList L, int i) {
LNode * p = GetElem(L, i - 1);
LinkList q;
q = p->next;
p->next = q->next;
free(q);
}
网友评论