顺序表和链表

2024-02-01 20:23:04

一、数据结构绪论基本概念

1.名词解释：

数据：对客观事物的符号表示
数据元素：数据的基本单位，可由若干个数据项组成
数据项：数据的不可分割的最小单位
数据对象：性质相同的数据元素的集合，是数据的子集
数据结构：相互之间存在特定关系的数据元素的集合（关系描述数据元素之间的逻辑关系）
物理结构（存储结构）：数据结构在计算机中的表示
数据类型：一个值的集合和定义在值集上的一组操作的总称
抽象数据类型：一个数学模型以及定义在该模型上的一组操作

2.算法的5个重要特性

有穷性、确定性、可行性、输入（有零个或多个）、输出（有一个或多个）

二、顺序表

1. 线性表的顺序表示及实现

问题1：线性表的长度（length）和分配的存储容量（listsize）的关系
当前长度是线性表元素的个数
存储容量是线性表能存放的元素的个数，以sizeof(ElemType)为单位

问题2：realloc函数的用法
函数声明void *realloc(void *ptr, size_t size)
指针指向需要重新分配内存的内存块
size为内存块新的大小

问题3：L->elem[i]写法的意思
malloc分配了一块内存空间，用指针进行访问，L->elem[i]即访问L->elem+i元素

问题4：for(int j=L->length-1;j>=i-1;j--)
元素下标从0开始，第一个元素下标为0

#include<stdio.h>
#include<malloc.h>
//动态分配顺序表存储结构
#define LIST_INIT_SIZE 80	//线性表存储空间的初始分配量
#define INCREMENT 10		//分配溢出时，线性表存储空间的增量
#define ERROR 0
#define OK 1
typedef int Elemtype;		//定义线性表元素的类型
typedef struct SqList{
	Elemtype *elem;			//线性表的基址
	int length;				//线性表的长度
	int listsize;			//当前分配的线性表存储容量
}SqList;

int InitList_Sq(SqList *L);	//初始化线性表
int CreatList_Sq(SqList *L,int n);	//构造长度为n的线性表
int ListInsert_Sq(SqList *L,int i,Elemtype e);	//在第i个元素前插入一个元素e
int ListDelete_Sq(SqList *L,int i);	//删除第i个元素
int ListLocate_Sq(SqList *L,Elemtype e);	//查找与e相等的元素
int PrintList_Sq(SqList *L);

int InitList_Sq(SqList *L){
	//构造一个新的线性表
	L->elem = (Elemtype*)malloc(LIST_INIT_SIZE*sizeof(Elemtype));	//分配空间
	if(!L->elem)	//分配空间失败
		return ERROR;
	L->length = 0;	//线性表的初始长度为0
	L->listsize = LIST_INIT_SIZE;
	return OK;
}

int CreatList_Sq(SqList *L,int n){
	//构造长度为n的线性表
	Elemtype e;
	for(int i=0;i<n;i++){
		printf("输入第%d个元素:\n",i+1);
		scanf("%d",&e);
		if(!ListInsert_Sq(L,i+1,e))	//插入元素失败
			return ERROR;
	}
	return OK;
}

int ListInsert_Sq(SqList *L,int i,Elemtype e){
	//在第i个元素前插入一个元素e
	if(i<1 || i>L->length+1){//i的值不合法
		return ERROR;
	}

	if(L->length >= L->listsize){  //存储空间已满，需要重新分配
		L->elem = (Elemtype*)realloc(L->elem, (LIST_INIT_SIZE + INCREMENT)*sizeof(Elemtype));
		if(!L->elem){
			return ERROR;
		}
		L->listsize = LIST_INIT_SIZE + INCREMENT;
	}
	//将插入位置及之后的元素后移，从最后一个元素开始后移
	for(int j=L->length-1;j>=i-1;j--){
		L->elem[j+1] = L->elem[j];
	}
	L->elem[i-1]=e;	//将e插在第i个位置
	L->length++;	//线性表的长度加1
	return OK;
}

int ListDelete_Sq(SqList *L,int i){
	//删除第i个元素
	if(i<1 || i>L->length+1){//i的值不合法
		return ERROR;
	}
	//将要删除元素后面的元素前移
	for(int j=i-1;j<=L->length-1;j++){
		L->elem[j] = L->elem[j+1];
	}
	L->length--;	//线性表的长度减1
	return OK;
}

int PrintList_Sq(SqList *L){
    for(int i=1;i<=L->length;i++)
        printf("%5d",L->elem[i-1]);
    return OK;
}

int ListLocate_Sq(SqList *L,Elemtype e){
	//在线性表中查找指定元素，返回元素位序
	int i=1;
	while(i<=L->length && L->elem[i-1]!=e){
		i++;
	}
	if(i<=L->length){
		return i+1;
	}
	else
		return -1;

}

int main(){
    SqList sl;
    int n,e,k;
    printf("输入顺序表元素的个数:\n");
    scanf("%d",&n);
    if(n>0)
    {
        printf("\n1-Creat\n");
        InitList_Sq(&sl);
        CreatList_Sq(&sl,n);
        printf("\n2-Insert\n");
        printf("输入要插入的元素和插入位置:\n");
        scanf("%d %d",&e,&k);
        ListInsert_Sq(&sl,k,e);
        PrintList_Sq(&sl);
        printf("\n3-Delete\n");
        printf("输入要删除的元素的位置:\n");
        scanf("%d",&k);
        ListDelete_Sq(&sl,k);
        PrintList_Sq(&sl);
    }
    else{
        printf("ERROR");
    }
	return 0;
}

三、线性表的单链表存储

头指针：头指针指向链表中第一个结点存储位置
头结点：第一个结点前，附设的一个结点
问题1:取第i个元素，第i个元素不存在if(!p || j>i)
p指向第1个元素，j=1，p与j保持同步（即p指向链表中第j个元素）
i的值不合法，即第i个元素不存在（i小于1或者大于表长）
问题2：删除第i个元素，循环终止条件
问题3：初始化、创建、销毁链表时，形参是二级指针

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

typedef int Elemtype;
typedef struct LNode{
	Elemtype data;
	struct LNode* next;
}LNode,*Linklist;

int CreatList_L(Linklist *L,int n);	//构造长度为n的链表
int GetElem_L(Linklist L,int i,Elemtype *e);	//取第i个元素,赋值给e
int ListInsert_L(Linklist L,int i,Elemtype e);	//在第i个位置之前插入e
int ListDelete_L(Linklist L,int i);	//删除第i个位置的元素
void Print_L(Linklist L);

int CreatList_L(Linklist *L,int n){
	*L = (Linklist)malloc(sizeof(LNode));
	(*L)->next = NULL;
	Linklist p;
	for(int i=n;i>0;--i){
        p = (Linklist)malloc(sizeof(LNode));
		printf("请输入第%d个元素\n",n-i+1);
		scanf("%d",&p->data);
		p->next = (*L)->next;
		(*L)->next = p;
	}
    return OK;
}

int GetElem_L(Linklist L,int i,Elemtype *e){
	//L为指向带头结点的头指针
	Linklist p=L->next;	//p指向第一个结点，寻找第i个元素
	int j=1;	//j为计数器，p与j同步
	while(p && j<i){		//循环终止条件p指向第i个元素或p为空
		p = p->next;
		j++;
	}
	if(!p || j>i)	//第i个元素不存在
		return ERROR;
	e = p->data;	///取第i个元素
	return OK;
}

int ListInsert_L(Linklist L,int i,Elemtype e){
	Linklist p=L,s;
	int j=0;
	while(p && j<i-1){	//寻找第i-1个元素
		p = p->next;
		j++;
	}
	if(!p || j>i-1){	//i小于1或大于表长+1
		return ERROR;
	}
	s = (LNode*)malloc(sizeof(LNode));	//生成新结点
	s->data = e;
	s->next = p->next;
	p->next = s;
	return OK;
}

int ListDelete_L(Linklist L,int i){
	Linklist p=L,q;
	int j=0;
	while(p->next && j<i-1){
		p = p->next;
		j++;
	}
	if(!(p->next) || j>i-1)
		return ERROR;
	q = p->next;
	p->next = q->next;
	free(q);
	return OK;
}

void Print_L(Linklist L){
	Linklist p;
	p = L->next;
	while(p!=NULL){
		printf("%5d",p->data);
		p = p->next;
	}
}

int main(){
	Linklist ll=NULL;
	int n,m,k;
	printf("输入链表元素个数:\n");
	scanf("%d",&n);
	if(n>0){
		printf("1-Creat");
		CreatList_L(&ll,n);
		Print_L(ll);
		printf("\n2-Insert\n");
        printf("输入要插入的元素和位置\n");
        scanf("%d %d",&k,&m);
        ListInsert_L(ll,m,k);
        Print_L(ll);
        printf("\n3-Delete\n");
		printf("输入要删除元素的位置\n");
		scanf("%d",&m);
		ListDelete_L(ll,m);
		printf("\nPrint\n");
		Print_L(ll);
	}
	else
        printf("ERROR");
	return 0;
}

参考博客：https://www.cnblogs.com/wkfvawl/p/9883872.html

码农公寓