- 一、线性表
- 1.1 线性表定义
- 1.2 顺序表定义
- 二、静态分配顺序表
- 2.1 顺序表结构及接口定义
- 2.2 顺序表初始化
- 2.3 头插元素
- 2.4 头删元素
- 2.5 尾插元素
- 2.6 尾删元素
- 2.7 指定位置插入元素
- 2.8 指定位置删除元素
- 2.9 查找指定元素下标
- 2.10 打印顺序表
- 2.11 程序源代码
线性结构是指结构中的数据元素之间存在着一对一的关系。线性结构的基本特征如下:
●有且只有一个“第一元素”;有且只有一个“最后元素”;
●除第一元素之外,其他元素都有唯一的直接前趋;.
●除最后元素之外,其他元素都有唯一的直接后继。
线性表是一种常用的、简单的数据结构,属于线性结构的范畴
1.1 线性表定义线性表(linear list)是具有相同数据类型的n(n>=0)个数据元素的有限a序列,通常记为
(a₁,a₂,…,aₙ₋₁,aₙ) 线性表的顺序存储是指用一组地址连续的内存单元依次存储线性表中的各个元素、使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系，采用顺序存储结构的线性表通常称为顺序表 数组下标从0开始，位置从1开始 下标从0开始，当有多个元素的值相同时，返回找到的第一个元素下标 头文件SeqList.h内容： 源文件SeqList.c内容： 源文件main.c内容：
其中,数据元素的个数n称为线性表的长度。当n=0时称为空表。从线性表的定义可以看出它的逻辑特征是:在非空的线性表中,有且只有一个起始结点(第一元素)a₁,它没有直接前趋,只有一个直接后继a₂;有且只有一个终端结点(最后元素)aₙ它没有直接后继,只有一个直接前趋aₙ₋₁;而除了a₁和aₙ外,其他的每一个结点aᵢ(2
在C语言中顺序表通过数组方式实现，数组的创建有两种方式。使用定长数组的方式称为静态分配顺序表，使用动态内存分配的方式称为动态分配顺序表。不了解动态内存分配可参考这篇博客https://blog.csdn.net/kjl167/article/details/123799963#define MAXSIZE 20 //数组大小
typedef int ElemType; //元素类型重定义，以后元素类型发生改变只用改这里
typedef struct SeqList
{
ElemType data[MAXSIZE];
int length; //顺序表当前长度（已存放元素个数）
}SeqList;
void InitSeq(SeqList* p); //顺序表初始化
void SeqListHeadInsert(SeqList* p, ElemType elem); //头部插入元素
void SeqListHeadDelete(SeqList* p); //头部删除元素
void SeqListTailInsert(SeqList* p, ElemType elem); //尾部插入元素
void SeqListTailDelete(SeqList* p); //尾部删除元素
void SeqListInsert(SeqList* p, int pos,ElemType elem); //插入元素到pos位置,位序从1开始算，数组下标从0开始
void SeqListDelete(SeqList* p, int pos); //删除pos位置元素,位序从1开始算，数组下标从0开始
int SeqListFind(SeqList* p, ElemType elem); //查找指定值并返回下标，未找到返回-1
void SeqListPrint(SeqList* p); //打印顺序表
2.2 顺序表初始化
void InitSeq(SeqList* p)
{
assert(p);
p->length = 0; //顺序表长度置为0
}
2.3 头插元素
void SeqListHeadInsert(SeqList* p, ElemType elem)
{
assert(p);
if (p->length == MAXSIZE)
{
printf("顺序表已满，插入失败n");
}
else
{
int i = p->length - 1; //最后一个元素下标
for (i; i >= 0; i--) //最后一个元素开始遍历所有元素分别将它们向后移动一个位置
{
p->data[i + 1] = p->data[i];
}
p->data[0] = elem; //将元素插入到顺序表头部
p->length++;
}
}
2.4 头删元素
void SeqListHeadDelete(SeqList* p)
{
assert(p);
if (p->length == 0)
{
printf("顺序表为空，删除失败n");
}
else
{
int i = 1; //第2个元素下标
for (i; i < p->length; i++) //从第2个元素位置开始遍历到最后一个元素，分别将它们都向前移动1个位置
{
p->data[i - 1] = p->data[i];
}
p->length--;
}
}
2.5 尾插元素
void SeqListTailInsert(SeqList* p, ElemType elem)
{
assert(p);
if (p->length == MAXSIZE)
{
printf("顺序表已满，插入失败n");
}
else
{
p->data[p->length] = elem;
p->length++;
}
}
2.6 尾删元素
void SeqListTailDelete(SeqList* p)
{
assert(p);
if (p->length == 0)
{
printf("顺序表为空，删除失败n");
}
else
{
p->length--; //只需将元素个数-1
}
}
2.7 指定位置插入元素
void SeqListInsert(SeqList* p, int pos,ElemType elem)
{
assert(p);
if (pos >= 1 && pos <= p->length+1) //当位置为1(表头)--表尾的后一个位置时合法
{
if (p->length == MAXSIZE)
{
printf("顺序表已满，插入失败n");
}
else
{
int i = p->length - 1; //最后一个元素下标
for (i; i >= pos - 1; i--) //pos-1为pos位置元素下标，从最后一个元素开始遍历到pos位置元素，分别将它们向后移动一个位置
{
p->data[i + 1] = p->data[i];
}
p->data[pos - 1] = elem;
p->length++;
}
}
else
{
printf("位置越界,插入失败n");
}
}
2.8 指定位置删除元素
void SeqListDelete(SeqList* p, int pos)
{
assert(p);
if (p->length == 0)
{
printf("顺序表为空，删除失败n");
}
else if(pos >= 1 && pos <= p->length)
{
int i = pos; //指定位置的后1个元素
for (i; i < p->length; i++)
{
p->data[i - 1] = p->data[i];
}
p->length--;
}
else
{
printf("位置越界,删除失败n");
}
}
2.9 查找指定元素下标
int SeqListFind(SeqList* p, ElemType elem)
{
assert(p);
int i = 0;
for (i = 0; i < p->length; i++)
{
if (p->data[i] == elem)
{
return i;
}
}
return -1;
}
2.10 打印顺序表
void SeqListPrint(SeqList* p)
{
assert(p);
if (p->length == 0)
{
printf("顺序表为空n");
return;
}
int i = 0;
for (i = 0; i < p->length; i++)
{
printf("%d ", p->data[i]);
}
printf("n");
}
2.11 程序源代码
#pragma once
#include
#include "SeqList.h"
void InitSeq(SeqList* p)
{
assert(p);
p->length = 0;
}
void SeqListHeadInsert(SeqList* p, ElemType elem)
{
assert(p);
if (p->length == MAXSIZE)
{
printf("顺序表已满，插入失败n");
}
else
{
int i = p->length - 1; //最后一个元素下标
for (i; i >= 0; i--) //最后一个元素开始遍历所有元素分别将它们向后移动一个位置
{
p->data[i + 1] = p->data[i];
}
p->data[0] = elem; //将元素插入到顺序表头部
p->length++;
}
}
void SeqListHeadDelete(SeqList* p)
{
assert(p);
if (p->length == 0)
{
printf("顺序表为空，删除失败n");
}
else
{
int i = 1; //第2个元素下标
for (i; i < p->length; i++) //从第2个元素位置开始遍历到最后一个元素，分别将它们都向前移动1个位置
{
p->data[i - 1] = p->data[i];
}
p->length--;
}
}
void SeqListTailInsert(SeqList* p, ElemType elem)
{
assert(p);
if (p->length == MAXSIZE)
{
printf("顺序表已满，插入失败n");
}
else
{
p->data[p->length] = elem;
p->length++;
}
}
void SeqListTailDelete(SeqList* p)
{
assert(p);
if (p->length == 0)
{
printf("顺序表为空，删除失败n");
}
else
{
p->length--; //只需将元素个数-1
}
}
void SeqListInsert(SeqList* p, int pos,ElemType elem)
{
assert(p);
if (pos >= 1 && pos <= p->length+1) //当位置为1(表头)--表尾的后一个位置时合法
{
if (p->length == MAXSIZE)
{
printf("顺序表已满，插入失败n");
}
else
{
int i = p->length - 1; //最后一个元素下标
for (i; i >= pos - 1; i--) //pos-1为pos位置元素下标，从最后一个元素开始遍历到pos位置元素，分别将它们向后移动一个位置
{
p->data[i + 1] = p->data[i];
}
p->data[pos - 1] = elem;
p->length++;
}
}
else
{
printf("位置越界,插入失败n");
}
}
void SeqListDelete(SeqList* p, int pos)
{
assert(p);
if (p->length == 0)
{
printf("顺序表为空，删除失败n");
}
else if(pos >= 1 && pos <= p->length)
{
int i = pos; //指定位置的后1个元素
for (i; i < p->length; i++)
{
p->data[i - 1] = p->data[i];
}
p->length--;
}
else
{
printf("位置越界,删除失败n");
}
}
int SeqListFind(SeqList* p, ElemType elem)
{
assert(p);
int i = 0;
for (i = 0; i < p->length; i++)
{
if (p->data[i] == elem)
{
return i;
}
}
return -1;
}
void SeqListPrint(SeqList* p)
{
assert(p);
if (p->length == 0)
{
printf("顺序表为空n");
return;
}
int i = 0;
for (i = 0; i < p->length; i++)
{
printf("%d ", p->data[i]);
}
printf("n");
}
#include "SeqList.h"
void menu()
{
printf("------------------------------n");
printf("-- H. 头插元素 h. 头删元素 --n");
printf("-- T. 尾插元素 t. 尾删元素 --n");
printf("-- I. 插入元素 D. 删除元素 --n");
printf("-- F. 查找元素 P. 打印元素 --n");
printf("--------- Q. 退出 --------n");
printf("------------------------------nn");
}
int main()
{
SeqList s = {0};
InitSeq(&s);
char choose = 'Q';
do
{
menu();
printf("请选择：");
choose = getchar(); //接受用户选择
ElemType elem; //待插入（或查找）元素值
int position = 0; //待插入（删除）元素位序
getchar(); //从输入缓冲区读取回车符，避免影响下次输入
switch (choose)
{
case 'H':
printf("请输入待插入元素值：");
scanf("%d", &elem);
SeqListHeadInsert(&s, elem);
getchar();
break;
case 'h':
SeqListHeadDelete(&s);
break;
case 'T':
printf("请输入待插入元素值：");
scanf("%d", &elem);
SeqListTailInsert(&s, elem);
getchar();
break;
case 't':
SeqListTailDelete(&s);
break;
case 'I':
printf("请输入待插入元素位序及值,例：2 5 >"); //位序：顺序表的第几个元素，从1开始
scanf("%d %d",&position,&elem);
SeqListInsert(&s,position,elem);
getchar();
break;
case 'D':
printf("请输入待删除元素位序：");
scanf("%d", &position);
SeqListDelete(&s, position);
getchar();
break;
case 'F':
printf("请输入待查找元素的值：");
scanf("%d", &elem);
int index = SeqListFind(&s, elem);
getchar();
if (index == -1)
{
printf("%d 不在顺序表中n",elem);
}
else
{
printf("%d 元素的下标为：%dn", elem, index);
}
break;
case 'P':
SeqListPrint(&s);
break;
case 'Q':
printf("退出成功n");
break;
default:
printf("选择错误，请重新选择!!!n");
break;
}
} while (choose != 'Q');
return 0;
}
