顺序表与链表的操作

继上一节C语言实现顺序表与链表创建可以知道顺序表是借助数组实现连续空间的处理，而在链表中每个结点是同一级别的变量，通过记录地址实现连接。

在线性表的抽象定义中还定义了对标的基本操作如下：

• 顺序表

#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 10
typedef struct{
	int item[MAXSIZE];
	int length;
}SeqList;


//初始化
int InitList(SeqList *L){
	//L->item = (int*)malloc(sizeof(int)*10);  动态分配数组
	L->item[0] = {};   //初始化
	L->length = 0;
	return 0;
}

//插入元素
int Insert(SeqList *L,int e,int n){
	if(n<1 || n>L->length) {   //插入位置大于当前删除在最后插入，输入位置无效
		L->item[n-1] = e;
		return 1;
	}
	if(L->length == MAXSIZE) return 0;
	for(int i =L->length-1;i>=0;i--){   //从i之后的位置元素整体后移
		L->item[i+1]= L->item[i];
	}
	L->item[n-1] = e;
	L->length++;
	return 1;
}

//删除
int Delete(SeqList *L,int n){
	if(n<1 || n>L->length) return 0;
	for(int i = n-1;i<L->length;i++){   //删除位置后面的元素整体前移
		L->item[i] = L->item[i+1];
	}
	L->length--;
	return 1;
}

//取值
int GetLocate(SeqList *L,int n){
	if(n<1 || n>MAXSIZE) return 0;
	int e = L->item[n-1];
	return e;
}

//查找
int Query(SeqList *L,int e){
	for(int i =0;i<L->length;i++){
		if(L->item[i] == e) return i+1;
	}
	return 0;
}


int main(){
	SeqList L;
	InitList(&L);
	Insert(&L,3,1);
	int e = GetLocate(&L,1);
	printf("%d",e);
}

• 链表

#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0

typedef struct LNode{
	int data;
	struct LNode *next;
}LNode,LinkList;


int main(){
	//生成链表
	LinkList* L = (LNode*)malloc(sizeof(LNode));
	//链表必须存在头指针
	LNode* head = L;
	printf("输入添加元素的个数:\n");
	int e,length;
	scanf("%d",&length);
	for(int i=0;i<length;i++){
		//创建新结点
		LNode* node = (LNode*)malloc(sizeof(LNode));
		printf("请输入：");
		scanf("%d",&e);
		node->data = e;
		node->next =NULL;
		head->next = node;
		head = node;     //头指正记录当前最后一个结点
	}	
	//打印链表
	while(L->next != NULL){
		L=L->next;
		printf("%d",L->data);
	}
}

在链表的创建时是在主函数中创建的，若干零散的变量通过指针联系在一起，那么要遵循模块化开发，都放在主函数是不合理的。此时就需要借助malloc函数了，该方法创建的变量存在于堆内存中，随程序的运行一直存在，就如同创建了一个全局变量。

因此，创建链表的步骤也可以模块化放入方法中执行了。

#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0

typedef struct LNode{
	int data;
	struct LNode *next;
}LNode,LinkList;

int InitList(LinkList *L);
int AddElem(LinkList *L,int e);
void dislapy(LinkList *L);
int CreateList(LinkList *L, int e);

int main(){
	
	LinkList *L;
	InitList(L);
	CreateList(L,3);
	printf("%s","fgdfdkjgfd");
	/*
	LinkList* L = &list;   //不可省略，不能直接传递
	InitList(L);
	AddElem(L,5);

	AddElem(&L,10);
	AddElem(&L,6);
	AddElem(&L,3);
	*/
	//dislapy(L);

	return 1;
}

//new是c++的初始化方法，c预言中改为malloc（用起来复杂）
int InitList(LinkList *L){
	L = (LNode*)malloc(sizeof(LNode));   //分配内存空间 c++使用new关键字
	L -> data = 0;
	L -> next = NULL;
	return 1;
}

int CreateList(LinkList *L, int e){
	//链表必须存在头指针
	LNode* head = L;
	//创建新结点
	LNode* node = (LNode*)malloc(sizeof(LNode));
	node->data = e;
	node->next =NULL;
	head->next = node;
	head = node;     //头指正记录当前最后一个结点
	
}

//插入
int InsertElem(LinkList *L,int e){
	//生成一个新节点 （malloc生成为全局变量）
	LNode *node = (LNode*)malloc(sizeof(LNode));
	//值赋值个新结点
	node->data = e;
	node->next = NULL;
	//将元素放到最后（尾插法特殊形式）
	while(L->next != NULL){
		L = L ->next;     //头结点指向下一个结点，判断是否为尾结点 （尾结点的指向NULL）
	}
	node->next = L->next;   //新结点的后继指针域指向尾结点的后置指针域
	L->next = node;   //尾结点后继结点指向新结点
	return OK;	
}

//删除
int DeleteElem(LinkList *L,int i){
	int j =0;
	LNode *p = L;
	while(L->next != NULL){
		j++;
		p = p->next;
		if(j == i){
			p->next = p->next->next;
			return 1;
		}
	}
	return 0;
}

//遍历
void dislapy(LinkList* L){
	while(L->next != NULL){
		//TODO
		printf("%d",L->data);
	}
}