线性表(顺序表和链表)

前言

#include <stdio.h>
#include <string.h>
typedef struct{
	int isbn;
	char bookName[20];
	double price;

}book;

int main()
{
	book b;
	b.isbn=121212;
	strcpy(b.bookName,"程序设计基础");
	b.price=34.7;
	printf("书名:%s",b.bookName);
	   
   return 0;
}

顺序表

#include <stdio.h>
#include <string.h>
#define MAXSIZE 100
typedef int ElemType;
typedef struct{
	ElemType data[MAXSIZE];
	int length;					 
}SeqList;

void initList(SeqList* L){
	L->length=0;
}



int appendElem(SeqList* L,ElemType e){
	if(L->length>=MAXSIZE){
		printf("顺序表已经满了\n");
		return 0;
	}
	L->data[L->length]=e;
	L->length++;
	return 1;
}

int insertElem(SeqList *L,int pos,ElemType e){
	if(L->length>=MAXSIZE){
		printf("顺序表已经满了\n");
		return 0;
	}
	if(pos<1||pos>L->length){
		printf("插入位置错误\n");
		return 0;
	}
	
	if(pos <= L->length){
		for(int i=L->length-1;i>=pos-1;i--){
			L->data[i+1]=L->data[i];
		}
		L->data[pos-1]=e;
		L->length++;
	}
	return 1;
}

int deleteElem(SeqList *L,int pos,ElemType* e){
	if(L->length==0){
		printf("空表\n");
		return 0;
	}
	
	if(pos<1 || pos>L->length){
		printf("删除数据位置有误\n");
		return 0;
	}
	
	*e=L->data[pos-1];
	if(pos<L->length){
		for (int i=pos;i<L->length;i++){
			L->data[i-1]=L->data[i];
		}
	
	}
	L->length--;
	return 1;

}

int findElem(SeqList *L,ElemType e){
	for(int i=0;i<L->length;i++){
		if(L->data[i]==e){
			return i+1;
		}
	}
	return 0;
}

void listElem(SeqList *L){
	for(int i=0;i<L->length;i++){
		printf("%d ",L->data[i]);
	}
	printf("\n");
}


int main()
{
	//顺序表初始化
	SeqList list;
	initList(&list);
	printf("初始化成功,目前长度占用%d\n",list.length);
	printf("目前占用内存%zu字节\n",sizeof(list.data));
	
	//添加元素
	appendElem(&list,88);
	appendElem(&list,55);
	appendElem(&list,77);
	appendElem(&list,22);
	listElem(&list);
	
	//插入元素  最好时间复杂度O(1) 最坏时间复杂度O(n)
	insertElem(&list,2,18);
	listElem(&list);
	
	//删除元素
	ElemType delData;
	deleteElem(&list,4,&delData);
	printf("被删除的数据为:%d\n",delData);
	listElem(&list);
	
	//查找
	printf("%d\n",findElem(&list,18));
	
	   
   return 0;
}

顺序表的动态初始化

#include <stdio.h>
#include<stdlib.h> //malloc
#include <string.h>
#define MAXSIZE 100
typedef int ElemType;
//动态分配内存地址初始化 
//只是在初始化和定义上不同 在堆内存中
typedef struct{
	ElemType *data;
	int length;
}SeqList;

SeqList* initList(){
	SeqList* L=(SeqList*)malloc(sizeof(SeqList));
	L->data=(ElemType*)malloc(sizeof(ElemType)*MAXSIZE);
	L->length=0;
	return L;
}


int appendElem(SeqList* L,ElemType e){
	if(L->length>=MAXSIZE){
		printf("顺序表已经满了\n");
		return 0;
	}
	L->data[L->length]=e;
	L->length++;
	return 1;
}

int insertElem(SeqList *L,int pos,ElemType e){
	if(L->length>=MAXSIZE){
		printf("顺序表已经满了\n");
		return 0;
	}
	if(pos<1||pos>L->length){
		printf("插入位置错误\n");
		return 0;
	}
	
	if(pos <= L->length){
		for(int i=L->length-1;i>=pos-1;i--){
			L->data[i+1]=L->data[i];
		}
		L->data[pos-1]=e;
		L->length++;
	}
	return 1;
}

int deleteElem(SeqList *L,int pos,ElemType* e){
	if(L->length==0){
		printf("空表\n");
		return 0;
	}
	
	if(pos<1 || pos>L->length){
		printf("删除数据位置有误\n");
		return 0;
	}
	
	*e=L->data[pos-1];
	if(pos<L->length){
		for (int i=pos;i<L->length;i++){
			L->data[i-1]=L->data[i];
		}
	
	}
	L->length--;
	return 1;

}

int findElem(SeqList *L,ElemType e){
	for(int i=0;i<L->length;i++){
		if(L->data[i]==e){
			return i+1;
		}
	}
	return 0;
}

void listElem(SeqList *L){
	for(int i=0;i<L->length;i++){
		printf("%d ",L->data[i]);
	}
	printf("\n");
}


int main()
{
	//顺序表初始化
	SeqList* list =initList();
	printf("初始化成功,目前长度占用%d\n",list->length);
	printf("目前占用内存%zu字节\n",sizeof(list->data));
	
	//添加元素
	appendElem(list,88);
	appendElem(list,55);
	appendElem(list,77);
	appendElem(list,22);
	listElem(list);
	
	//插入元素  最好时间复杂度O(1) 最坏时间复杂度O(n)
	insertElem(list,2,18);
	listElem(list);
	
	//删除元素
	ElemType delData;
	deleteElem(list,4,&delData);
	printf("被删除的数据为:%d\n",delData);
	listElem(list);
	
	//查找
	printf("%d\n",findElem(list,18));
	
	   
   return 0;
}

单链表

#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
//定义
typedef struct node{
	ElemType data;
	struct node* next;
}Node;

//初始化
Node* initList(){
	Node* head=(Node*)malloc(sizeof(Node));
	head->data=0;
	head->next=NULL;
	return head;
}

//头插法
int insertHead(Node* L,ElemType e){
	Node* p=(Node*)malloc(sizeof(Node));
	p->data=e;
	p->next=L->next;
	L->next=p;
	return 1;
}
Node* get_tail(Node* L){
	Node* p=L;
	while(p->next != NULL){
		p=p->next;
	}
	return p;
}
//尾插法
Node* insertTail(Node* tail,ElemType e){
	Node* p=(Node*)malloc(sizeof(Node));
	p->data=e;
	tail->next=p;
	p->next=NULL;
	return p;
}

//在指定位置插入数据
int insertNode(Node* L,int pos,ElemType e){
	Node* p=L;
	int i=0;
	while(i<pos-1){
		p=p->next;
		i++;
		if(p==NULL){
			return 0;
		}
	}
	
	//要插入的新节点
	Node* q=(Node*)malloc(sizeof(Node));
	q->data=e;
	q->next=p->next;
	p->next=q;
	return 1;

}

//删除节点
int deleteNode(Node* L,int pos){
	//p :要删除节点的前驱
	Node* p=L;
	int i=0;
	while(i<pos-1){
		p=p->next;
		i++;
		if(p==NULL){
			return 0;
		}
	}
	
	if(p->next ==NULL){
		printf("要删除的位置错误!\n");
		return 0;
	
	}
	//q指向要删除的节点
	Node* q=p->next;
	p->next=q->next;
	free(q);
	return 1;
}

//获取链表的长度
int listLength(Node* L){
	Node* p=L;
	int len=0;
	while(p!=NULL){
		p=p->next;
		len++;
	}
	return len-1;
}


//释放链表
void freeList(Node* L){
	Node* p=L->next;
	Node* q;
	
	while(p!=NULL){
		q=p->next;
		free(p);
		p=q;
	}
	L->next=NULL;
}

//遍历
void listNode(Node* L){
	Node* p=L->next;
	while(p != NULL){
		printf("%d ",p->data);
		p=p->next;
	}
	printf("\n");
}


int main()
{
  	Node* list=initList();
	// 头插法
	// insertHead(list,10);
	// insertHead(list,20);
	// insertHead(list,30);
	// listNode(list);
	
	//尾插法
	Node* tail=get_tail(list);
	tail = insertTail(tail,10);
	tail = insertTail(tail,20);
	tail = insertTail(tail,30);
	listNode(list);
	
	//插入节点
	insertNode(list,2,18);
	listNode(list);
	
	//删除节点
	deleteNode(list,2);
	listNode(list);
	
	//获取链表的长度
	int len=listLength(list);
	printf("链表的长度:%d\n",len);
	
	//释放链表
	freeList(list);
	int len2=listLength(list);
	printf("链表的长度:%d\n",len2);

   return 0;
}