数据结构学习(二)——线性表链式存储-使用c语言实现(手打)

时间:2022-10-03 10:17:38
#include<stdio.h>
#include<stdlib.h>//stdlib 头文件即standard library标准库头文件   stdlib 头文件里包含了C、C++语言的最常用的系统函数
#define OK 1
#define ERROR 0
typedef int ElemType;//使用typedef时要记住,typedef并没有创建任何新类型,它只是为某个已存在的类型增加一个方便使用的标签。
typedef int Status;

//线性表的单链表存储结构
typedef struct	Node {
	ElemType data;//数据域
	struct Node *next;//指针域 c语言中指针都是占32bit或者64bit的数据
}Node;

typedef struct Node *LinkList;//定义 LinkList

//获取链表的长度
Status getListLength(LinkList L) {
	int i = 0;//计数器
	while (L->next)//指针L所指节点中的成员next的是值,若该值为下一个节点的地址既循环条件为真,若是0或null则为假。
	{
		L = L->next;//把L的下一个节点赋值给L;
		i++;
	}
	return i;
}
//单链表的读取
//用e返回L中第i个数据元素的值 时间复杂度O(n);
Status getElem(LinkList L, int i, ElemType *e) {
	int j = 1;//计数器
	LinkList p;//声明一个节点p
	p = L->next;//让p指向L的第一个节点
	while (p&&j<i)//p不为空或者计数器还没有等于i时继续循环
	{
		p = p->next;//让p指向下一个节点
		j++;//自加
	}
	if (!p || j > i) {//第i个元素不存在
		return ERROR;
	}
	*e = p->data;//取第i个数据
	return OK;
}

// 在L中第i个位置前插入新的数据元素e
Status ListInsert(LinkList *L, int i, ElemType e) {
	int j;
	LinkList p, s;
	p = *L;//头指针L付给p
	j = 1;
	
	while (p&&j<i)//寻找第i个节点
	{
		p = p->next;
		j++;
	}
	if (!p||j > i) //第i个元素不存在
		return ERROR;
		//(指针类型) malloc(内存大小)——》返回一个指针(找一片指定大小的空间,然后将这片空间的首地址给一个指针变量)
	    s = (LinkList) malloc (sizeof(Node));//生成新节点
		s->data = e;//将新节点的数据域赋值为e
		s->next = p->next;//将p的后继节点赋值给s的后继节点
		p->next = s;//将s赋值给p的后继
		return OK;
}
//删除L的第i个元素,并用e返回其值,L的长度剪1;
Status ListDelete(LinkList *L, int i, ElemType *e) {
	int j = 1;
	LinkList p,q;
	p = *L;//头指针付给L
	while (p&&j<i)
	{
		p = p->next;
		j++;
	}
	if (!(p->next) || j > i) {//第i个元素不为空
		return ERROR;
	}
	q = p->next;//q表示第i个元素
	p->next = q->next;//第i-1的next赋到i+1上即i的next
	*e = q->data;//将q节点的数据给e
	free(q);//让系统回收此节点释放内存
	return OK;
}

//随机产生N个元素的值,建立带表 头结点 的单链线性表L(头插法)
void CrateListHead(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 CreatListTail(LinkList *L, int n) {
	LinkList p,r;
	int i;
	srand(time(0));
	*L = (LinkList)malloc(sizeof(Node));
	(*L)->next = NULL;//L是指整个单链表,而r是尾部节点的变量
	r = *L;//r为指向L尾部的节点
	for (i = 0; i < n; i++) {
		p = (LinkList)malloc(sizeof(Node));
		p->data = rand() % 100 + 1;
		r->next = p;//让尾部节点指向p,即p插入到最后
		r = p;//然后将p付给r,此时r又为尾部节点
	}
	r->next = NULL;//当循环结束后,将尾部节点r指向null
}

Status ClearList(LinkList *L) {//清空表L ,L存在
	LinkList p,q;
	int i = 0;
	p = (*L)->next;//p指向第一个节点
	while (p)//p不为空
	{
		q = p->next;//把 p的下一个节点付给 q
		free(p);//释放P;
		p = q;//把q赋值给p
	}
	(*L)->next = NULL;
	return OK;
}

void TrvalList(LinkList *L) {//打印链表L中所有的 元素
	LinkList p;
	p = (*L)->next;
	while (p)
	{
		printf("%d", p->data);
		printf(" ");
		p = p->next;
	}
}



int main(void) {
	LinkList L;
	int a;
	CreatListTail(&L, 10);
	TrvalList(&L);
	getchar();
	return 0;
}