编写单链表类模板,实现链表的创建、遍历,链表结点的插入、删除、查找...
发布网友
共1个回答
热心网友
#include<stdio.h>
#include<stdlib.h>
#include <time.h>
#define MAXSIZE 20
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int ElemType;
typedef int Status;
typedef struct Node {
ElemType data;
struct Node *next;
} Node;
typedef struct Node *Linklist;
//初始化链表
Status InitList(Linklist *L) {
*L = (Linklist) malloc(sizeof(Node));
if ((*L) == NULL)
return ERROR;
(*L)->next = NULL;
return OK;
}
//判断是否为空
Status Isempty(Linklist L) {
if (L->next)
return FALSE;
else
return TRUE;
}
//清空链表
Status ClearList(Linklist *L) {
Linklist p, q;
p = (*L)->next;//指向第一个结点
while (p) {
q = p->next;
free(p);
p = q;
}
(*L)->next = NULL;
return OK;
}
//返回链表长度
int GetLength(Linklist L) {
int i = 0;
Linklist p;
p = L->next;//指向第一个结点
while (p) {
i++;
p = p->next;//依次向后移
}
return i;
}
//用e返回第i个元素的值
Status GetElem(Linklist L, int i, ElemType *e) {
int j = 1;//计数器
Linklist p;
p = L->next;
while (p && j < i) {
p = p->next;
j++;
}
if (!p || j > i)
return ERROR;
*e = p->data;
return OK;
}
//获取和e相同值的序列
int Location(Linklist L, ElemType e) {
int i = 0;
Linklist p;
p = L->next;
while (p) {
i++;
if (p->data == e)
return i;
p = p->next;
}
return 0;
}
//在第i个元素之前插入数据e
Status InsertElem(Linklist *L, int i, ElemType e) {
int j = 1;
Linklist p, s;
p = (*L);
while (p && j < i) {
p = p->next;
j++;
}
if (!p || j > i)
return ERROR;
s = (Linklist) malloc(sizeof(Node));
s->data = e;
s->next = p->next;
p->next = s;
return OK;
}
//删除第i个元素，删除的值赋给e
Status DeleteElem(Linklist *L, int i, ElemType *e) {
int j = 1;
Linklist p, q;
p = *L;
while (p->next && j < i) {
p = p->next;
j++;
}
if (!(p->next) || j > i)
return ERROR;
q = p->next;
p->next = q->next;
*e = q->data;
free(q);
return OK;
}
//遍历链表
Status VisitList(Linklist L) {
Linklist p;
p = L->next;
while (p) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
return OK;
}
//随机产生n个元素，头插法
void CreateListHead(Linklist *L, int n) {
Linklist p;
int i;
srand(time(0));
*L = (Linklist) malloc(sizeof(Node));
(*L)->next = NULL;//生成一个带头结点的链表
for (i = 0; i < n; i++) {
p = (Linklist) malloc(sizeof(Node));//生成新的结点
p->data = rand() % 100 + 1;//随机生成100内的数字
p->next = (*L)->next;
(*L)->next = p;
}
}
//尾插法
void CreateListTail(Linklist *L, int n) {
Linklist r, p;
int i;
*L = (Linklist) malloc(sizeof(Node));
r = *L;
for (i = 0; i < n; i++) {
p = (Linklist) malloc(sizeof(Node));//生成新的结点
p->data = rand() % 100 + 1;//随机生成100内的数字
r->next = p;
r = p;
}
r->next = NULL;
}
//在尾部插入数据
void TailInsert(Linklist *L, ElemType e) {
Linklist p, q;
p = (*L);
while (p->next != NULL) {
p = p->next;
}
q = (Linklist) malloc(sizeof(Node));
q->data = e;
p->next = q;
q->next = NULL;
}
void Destroy(Linklist *L) {
Linklist p, q;
p = *L;
int n = 0;
while (p) {
q = p->next;
free(p);
p = q;
n++;
}
printf("销毁了%d个结点\n", n);
*L = NULL;//最后将*L的内容置为null，这样主函数中的链表list就为空了，防止了list变为野指针，而且链表在内存中也被完全的释放掉了。
}
int main() {
Linklist L;
ElemType e;
printf("插入5个数据：");
InitList(&L);
for (int j = 1; j <= 5; j++)
InsertElem(&L, 1, j * j);
VisitList(L);
if (Isempty(L) == TRUE)
printf("链表为空\n");
else
printf("链表不为空\n");
int n = GetLength(L);
printf("链表长度为:%d\n", n);
int m = Location(L, 9);
printf("9在第%d号位置\n", m);
GetElem(L, 5, &e);
printf("第五个元素为:%d\n", e);
DeleteElem(&L, 2, &e);
printf("删除第2个元素的值为：%d，删除后链表序列为:\n", e);
VisitList(L);
ClearList(&L);
printf("清空链表成功！\n");
CreateListHead(&L, MAXSIZE);
printf("头插法插入20个数据:\n");
VisitList(L);
ClearList(&L);
CreateListTail(&L, MAXSIZE);
printf("尾插法插入20个数据:\n");
VisitList(L);
printf("最后插入一个数据：\n");
TailInsert(&L, 15);
VisitList(L);
printf("_______\n");
Destroy(&L);
printf("链表销毁成功");
return 0;
}
