如何C语言编写线性表的初始化，求线性表长度，插入，删除_百度知道随笔 - 272&
评论 - 448&
&&&&&&&&&&&
十月份就要考数据结构了，为了这次考试能顺利通过。同时数据结构在开发过程中也是相当重要的，但是以前从来就没有系统地学习过。所以正好借此机会好好地学习下数据结构，一方面是为了通过考试，另一方面也把数据结构和算法这一块的基础打牢一点，真是一举两得啊。
我打算把这一部分写成一个系列，分为C#和C语言两个版本，每周发布两篇。从线性表开始，这一篇主要总结线性表之顺序表的相关操作，主要分以下几个部分来总结。
1，什么是线性表？
2，线性表的两种存储结构？
3，顺序表的存储结构表示？  4，顺序表的常见操作和代码实现？
1，什么是线性表
线性表就是关系中的一对一的关系，如果是一对多就用树来表示，如果多对多就用网状来表示。
线性表具有以下四个特征：
1& 有且只有一个“首”元素
2& 有且只有一个“尾”元素
3& 除“首”元素外，其余元素都有唯一的后继元素。
4& 除“尾”元素外，其余元素都有唯一的前驱元素。
2，线性表的两种存储结构
1& 顺序表，即线性表用顺序存储结构保存数据，数据是连续的。这一篇文章总结的就是顺序表
2& 链表，即线性表用链式存储结构保存数据，数据不连续。
3，顺序表的存储结构表示
注：C#和C语言中的数组下标都是从0开始的。
4，顺序表的常见操作和代码实现
顺序表主要有以下常见操作，我们一般用数组来保存数据
思路：将数组的长度length设为0，时间复杂度为O(1)。
2，求顺序表的长度
思路：获取数组的length值，时间复杂度为O(1)。
3，插入元素
思路：分两种情况，一种是插入位置在数组的末尾，这种情况与添加元素相同。另一种情况是插入位置在数组的开始，这时候被插入元素的后续元素都要依次向后移动一位，也就是说整个数组都会移动，所以时间复杂度为O(n)。
4，删除元素
思路：同样分两种情况，一种是删除位置在数组的末尾，不用移动任何元素，因此时间复杂度为O(1);另一种情况是删除位置在数组的开始，这时被删除元素的后续元素都要依次向前移动一位，因此时间复杂度为O(n)。
5，按序号查找元素
思路：因为顺序表的存储地址是连续的，所以第n个元素的地址公式为：(n-1)*单元存储长度，不用移动任何元素，因此时间复杂度为O(1)。
6，按关键字查找元素
思路：一般用for循环，调用IComparable接口的CompareTo()方法去比较，因此时间复杂度为O(n)。
项目结构：
实现代码：
namespace DS.Model
/// &summary&
/// 学生实体
/// &/summary&
public class Student
public int ID { get; set; }
public string Name { get; set; }
public int Age { get; set; }
namespace DS.BLL
/// &summary&
/// 顺序表操作业务逻辑类
/// &/summary&
public class SeqListBLL
/// &summary&
/// 初始化
/// &/summary&
/// &typeparam name=&T&&&/typeparam&
/// ¶m name=&seqListType&&&/param&
public static void InitSeqList&T&(SeqListType&T& seqList)
seqList.ListLen = <span style="color: #;
/// &summary&
/// 获取顺序表的长度
/// &/summary&
/// &typeparam name=&T&&&/typeparam&
/// ¶m name=&seqList&&&/param&
/// &returns&&/returns&
public static int GetSeqListLen&T&(SeqListType&T& seqList)
return seqList.ListL
/// &summary&
/// 插入元素(在第n个元素之前的位置插入新元素)
/// &/summary&
/// &typeparam name=&T&&&/typeparam&
/// ¶m name=&seqList&&&/param&
/// ¶m name=&n&&&/param&
/// ¶m name=&data&&&/param&
/// &returns&&/returns&
public static bool Insert&T&(SeqListType&T& seqList, int n, T data)
//检查数组是否已满
if (seqList.ListLen &= seqList.MaxSize) return false;
//检查n的位置是否超出范围
if (n & <span style="color: # || n & seqList.ListLen + <span style="color: #) return false;
//若插入数据位置不在表尾
if (n &= seqList.ListLen)
//将要插入位置之后元素依次向后移动一位
for (int i = seqList.ListLen - <span style="color: #; i &= n-<span style="color: #; i--)
seqList.ListData[i + <span style="color: #] = seqList.ListData[i];
//将数据插入到位置为n的位置并将数组的长度加1
seqList.ListData[n-<span style="color: #] =
seqList.ListLen++;
return true;
/// &summary&
/// 删除元素(删除第n个元素)
/// &/summary&
/// &typeparam name=&T&&&/typeparam&
/// ¶m name=&seqList&&&/param&
/// ¶m name=&n&&&/param&
/// &returns&&/returns&
public static bool Delete&T&(SeqListType&T& seqList, int n)
//判断数组是否为空
if (seqList.ListLen == <span style="color: #) return false;
//判断n的位置是否合法
if (n & <span style="color: # || n & seqList.ListLen) return false;
//如果删除不是最后位置
if (n & seqList.ListLen)
//将删除位置后继元素依次前移
for (int i = i & seqList.ListL i++)
seqList.ListData[i-<span style="color: #] = seqList.ListData[i];
seqList.ListLen--;
return true;
/// &summary&
/// 查找第n个元素
/// &/summary&
/// &typeparam name=&T&&&/typeparam&
/// ¶m name=&seqList&&&/param&
/// ¶m name=&n&&&/param&
/// &returns&&/returns&
public static T GetDataByIndex&T&(SeqListType&T& seqList, int n)
//检查位置是否超出范围
if(n&<span style="color: #||n&seqList.ListLen) return default(T);
return seqList.ListData[n-<span style="color: #];
/// &summary&
/// 按关键字查找元素
/// &/summary&
/// &typeparam name=&T&&&/typeparam&
/// &typeparam name=&W&&&/typeparam&
/// ¶m name=&seqList&&&/param&
/// ¶m name=&key&&&/param&
/// ¶m name=&where&&&/param&
/// &returns&&/returns&
public static T GetDataByKey&T, W&(SeqListType&T& seqList,string key,Func&T,W& where) where W : IComparable
for (int i = <span style="color: #; i & seqList.ListL i++)
if (where(seqList.ListData[i]).CompareTo(key) == <span style="color: #)
return seqList.ListData[i];
return default(T); //值类型返回0，引用类型返回null
/// &summary&
/// 封装顺序表
/// &/summary&
/// &typeparam name=&T&&&/typeparam&
public class SeqListType&T&
private const int maxSize = <span style="color: #0;
public int MaxSize { get { return maxS } }//表的最大长度
//初始化长度为100的数组保存数据
public T[] ListData = new T[maxSize];
//顺序表的长度
public int ListLen { get; set; }
namespace SeqList.CSharp
class Program
static void Main(string[] args)
//定义一个顺序表实例
SeqListType&Student& seqList = new SeqListType&Student&();
Console.WriteLine(&****************初始化**********************\n&);
SeqListBLL.InitSeqList&Student&(seqList);
Console.WriteLine(&初始化后表的长度为：{0}&,SeqListBLL.GetSeqListLen&Student&(seqList));
//插入数据
Console.WriteLine(&\n****************插入三条数据**********************\n&);
if (!SeqListBLL.Insert&Student&(seqList, <span style="color: #, new Student { ID = <span style="color: #, Name = &james&, Age = <span style="color: # })) Console.WriteLine(&插入失败&);
else Console.WriteLine(&插入成功&);
if (!SeqListBLL.Insert&Student&(seqList, <span style="color: #, new Student { ID = <span style="color: #, Name = &kobe&, Age = <span style="color: # })) Console.WriteLine(&插入失败&);
else Console.WriteLine(&插入成功&);
if (!SeqListBLL.Insert&Student&(seqList, <span style="color: #, new Student { ID = <span style="color: #, Name = &wade&, Age = <span style="color: # })) Console.WriteLine(&插入失败&);
else Console.WriteLine(&插入成功&);
Display(seqList);
//删除数据
Console.WriteLine(&\n****************删除一条数据**********************\n&);
SeqListBLL.Delete&Student&(seqList,<span style="color: #);
Console.WriteLine(&删除成功&);
Display(seqList);
//查找元素
Console.WriteLine(&****************查找元素by位置**********************\n&);
Console.WriteLine(&查找第{0}个元素&,<span style="color: #);
Student student= SeqListBLL.GetDataByIndex&Student&(seqList,<span style="color: #);
if (student != null) Console.WriteLine(&ID:& + student.ID + &,Name:& + student.Name + &,Age:& + student.Age);
else Console.WriteLine(&没有找到数据&);
//查找元素by关键字
Console.WriteLine(&****************查找元素by关键字**********************\n&);
Console.WriteLine(&查找关键字为{0}的元素&, &kobe&);
Student student1 = SeqListBLL.GetDataByKey&Student, string&(seqList,&kobe&,p=&p.Name);
if (student1 != null) Console.WriteLine(&ID:& + student1.ID + &,Name:& + student1.Name + &,Age:& + student1.Age);
else Console.WriteLine(&没有找到数据&);
//获取表的长度
Console.WriteLine(&****************获取表的当前长度**********************\n&);
int currentLen= SeqListBLL.GetSeqListLen&Student&(seqList);
Console.WriteLine(&当前表中有{0}个元素&, currentLen);
Display(seqList);
Console.ReadKey();
/// &summary&
/// 显示数据
/// &/summary&
/// ¶m name=&seqList&&顺序表对象&/param&
private static void Display(SeqListType&Student& seqList)
Console.WriteLine(&****************展示数据**********************&);
if (seqList == null || seqList.ListLen == <span style="color: #)
Console.WriteLine(&没有数据&);
for (int i = <span style="color: #; i & seqList.ListL i++)
Console.WriteLine(&ID:& + seqList.ListData[i].ID + &,Name:& + seqList.ListData[i].Name + &,Age:& + seqList.ListData[i].Age);
运行结果：
/*包含头文件*/
#include &stdio.h&
#include &stdlib.h&
#include &io.h&
#include &math.h&
#include &time.h&
/*定义常量，类似于C#中的const*/
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20
/*定义类型的同义字*/
typedef int S
typedef int ElemT
typedef struct //定义顺序表
ElemType data[MAXSIZE];
/*初始化*/
Status InitSeqList(SeqList *seqList) //*L表示指向顺序表SeqList的指针
seqList-&length=<span style="color: #;
return OK;
/*求顺序表的长度*/
int GetSeqListLen(SeqList *seqList)
return seqList-&
/*插入元素(在第n个元素之前的位置插入新元素)*/
Status Insert(SeqList *seqList,int n,ElemType e)
//检查数组是否已满
if (seqList-&length&=MAXSIZE) return ERROR;
//检查n的位置是否超出范围
if (n&<span style="color: #||n&seqList-&length+<span style="color: #) return ERROR;
//若插入数据位置不在表尾
if (n&=seqList-&length)
//将要插入位置之后元素依次向后移动一位
for (k=seqList-&length-<span style="color: #;k&=n-<span style="color: #;k--)
seqList-&data[k+<span style="color: #]=seqList-&data[k];
//将新元素插入到腾出的位置，并将表长加1
seqList-&data[n-<span style="color: #]=e;
seqList-&length++;
return OK;
/*删除元素(删除第n个元素)*/
Status Delete(SeqList *seqList,int n,ElemType *e)
//判断数组是否为空
if (seqList-&length==<span style="color: #) return ERROR;
//判断n的位置是否合法
if (n&<span style="color: #||n&seqList-&length) return ERROR;
*e=seqList-&data[n-<span style="color: #];
//如果删除不是最后位置
if (n&seqList-&length)
//将删除位置后继元素依次前移
for (k=n;k&seqList-&k++)
seqList-&data[k-<span style="color: #]=seqList-&data[k];
seqList-&length--;
return OK;
/*查找第n个元素*/
int GetDataByIndex(SeqList *seqList,int n)
//检查位置是否超出范围
if (n&<span style="color: #||n&seqList-&length) return ERROR;
return seqList-&data[n-<span style="color: #];
/*打印结果*/
void Display(SeqList *seqList)
printf(&\n********展示数据********\n&);
for (i=<span style="color: #;i&seqList-&i++)
Visit(seqList-&data[i]);
printf(&\n&);
Status Visit(ElemType c)
printf(&%d\n&,c);
return OK;
void main()
//声明变量
SeqList seqL //创建顺序表
printf(&\n*****************初始化************************\n&);
i=InitSeqList(&seqList);//&表示地址
printf(&初始化后表的长度为：%d\n&,seqList.length);
printf(&\n*****************插入五条数据************************\n&);
for (j=<span style="color: #;j&=<span style="color: #;j++)
i=Insert(&seqList,<span style="color: #,j);//在表头依次插入1~5
Display(&seqList);
printf(&\n*****************删除一条数据************************\n&);
i=Delete(&seqList,<span style="color: #,&elem);
if (i==OK) printf(&删除成功\n&);
Display(&seqList);
printf(&\n*****************查找元素by位置************************\n&);
k=GetDataByIndex(&seqList,<span style="color: #);
printf(&第2个元素为%d\n&,k);
printf(&\n*****************获取表的当前长度************************\n&);
k=GetSeqListLen(&seqList);
printf(&当前表中有%d个元素\n&,k);
getchar();
运行结果：
阅读(...) 评论()顺序表的初始化是建立一个空的线性表，那么........._数据结构吧_百度贴吧
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&签到排名：今日本吧第个签到，本吧因你更精彩，明天继续来努力！
本吧签到人数：0成为超级会员，使用一键签到本月漏签0次！成为超级会员，赠送8张补签卡连续签到：天&&累计签到：天超级会员单次开通12个月以上，赠送连续签到卡3张
关注：39,070贴子：
顺序表的初始化是建立一个空的线性表，那么.........收藏
那建立一个空表就包含了建表和初始化吗，能不能分成两个函数一个建表一个初始化？
数据加密系统防护8大行业配套解决方案,部署30家世界500强企业.免费咨询:400-898-1617
登录百度帐号推荐应用
为兴趣而生，贴吧更懂你。或求一个线性表的基本操作的编程建立单链表，基本操作包括：初始化，建立一个链式存储的链表，输出顺序表，判断是否为空，取表中第i个元素，定位函数（返回第一个与x相等的元素位置），插入，删除。1． 假设有两个按数据元素值非递减有序排列的线性表A和B，均以顺序表作为存储结构。编写算法将A表和B表归并成一个按元素值非递增有序（允许值相同）排列的线性表C。（可以利用将B中元素插入A中，或新建C表）2． 假设有两个按数据元素值非递减有序排列的线性表A和B，均以单链表作为存储结构。编写算法将A表和B表归并成一个按元素值递减有序（即非递增有序，允许值相同）排列的线性表C。
严蔚敏的书好好看看，都有的。至于你要能编译的代码，估计你去看高一凡的书，那本书是交大出版社出版的。那个很详细的哦。
为您推荐：
扫描下载二维码一个关于数据结构的问题设计一个顺序结构线性表，实现如下操作：1）SETNULL(L) 初始化，构造一个空的线性表 2）LENGTH(L) 求长度,返回线性表中数据元素个数 3）GET(L,i) 取表L中第i个数据元素的值 4）LOCATE(L,x) 按值查找，若表中存在一个或多个值为x的结点，返回第一个找到的数据元素的位序，否则返回一个特殊值。 5）INSERT(L,x,i) 在L中第i个位置新的数据元素x，表长加1。 6）DELETE(L,i) 删除表中第i个数据元素，表长减1。
这是我自己实现顺序表12种数据操作的源代码，你看看/********************** 声明部分 **********************/#include #include #include #include #include #define ElemType int/********************** 结构体定义部分 **********************/typedef struct{ ElemType *} SqL/********************** 函数块部分 **********************//********************** 构造一个空的线性表 **********************/void InitList(SqList &L){ L.elem=(ElemType *)malloc(100*sizeof(ElemType)); if(!L.elem)
exit(0); L.length=0; L.listsize=100;}/***************销毁线性表*****************/void DestroyList(SqList &L){ free(L.elem); L.elem=NULL; L.length=0; L.listsize=0;}/**************清空线性表**************/void ClearList(SqList &L){ L.length=0;}/*******判断线性表是否空*******/int ListEmpty(SqList L){ return(L.length==0);}/************返回线性表的长度************/int ListLength(SqList L){ return(L.length);}/********************** 用e返回L中第i个元素的值 **********************/int GetElem(SqList L,int i,ElemType &e){ if (iL.length)
return 0; e=*(L.elem+i-1); return 1;}/**************查找元素的位置**************/int LocateElem(SqList L, ElemType e,
int (*compare)(ElemType, ElemType)) {
ElemType *p;
while (i <= L.length && !(*compare)(*p++, e))
if (i <= L.length)
else return 0;} /***********用pre_e返回cur_e的前驱************/int PriorElem(SqList L,ElemType cur_e,ElemType &pre_e)//{ int i=2; ElemType *p=L.elem+1; while(i<=L.length&&*p!=cur_e) {
if(i>L.length)
return -1; else {
pre_e=*--p;
return 1; }}/************next_e返回cur_e的后继*************/int NextElem(SqList L,ElemType cur_e,ElemType &next_e){ int i=1; ElemType *p=L. while(i<=L.length&&*p!=cur_e) {
if(i==L.length)
return -1; else {
next_e=*++p;
return 1; }}/********************** 在L中第i个位置之前插入新的数据元素e，L的长度加1 **********************/int ListInsert(SqList &L, int i, ElemType e){
ElemType *p;
L.length+1) return 0;
if (L.length >= L.listsize)
ElemType *newbase = (ElemType *)realloc(L.elem,
(L.listsize+2)*sizeof (ElemType));
if (!newbase) return 0;
L.listsize += 2;
ElemType *q = &(L.elem[i-1]);
for(p = &(L.elem[L.length-1]);p>=q; --p)
*(p+1) = *p;
return 1;}/********************** 删除L的第i个元素，并用e返回其值，L的长度减1 **********************/int ListDelete(SqList &L, int i, ElemType &e) {
ElemType *p, *q;
if (iL.length)
p = &(L.elem[i-1]);
q = L.elem+L.length-1;
for (++p; p<=q; ++p)
*(p-1) = *p;
return 1;} /********************************以此对L的每个数据元素调用函数vi()*****************************/void ListTraverse(SqList L,void(*vi)(ElemType&)){ ElemType *p; p=L. for(i=1;i<=L.i++)
vi(*p++); printf("\n");}/************比较功能函数***************/int equal(int c1,int c2){ if(c1==c2)
return 1; else
return 0;}/*********************输出格式（%d）*********************/ void print(int &c){ printf("%d ",c);}void main(){ SqList L; ElemType e,e0; int j,k; printf("//////////////////////////////////\n"); printf("
现在进行线性表操作\n");
printf("//////////////////////////////////\n\n");
InitList(L);
printf("创建成功！\n"); printf("初始化L后：L.elem=%u L.length=%d\nL.listsize=%d\n",L.elem,L.length,L.listsize);
for(j=1;j<=5;j++)
i=ListInsert(L,1,j); printf("在L的表头依次插入1~5后：*L.elem="); for(j=1;j<=5;j++)
cout<<*(L.elem+j-1)<<" ";
cout<< printf("L.elem=%u L.length=%d L.listsize=%d \n",L.elem,L.length,L.listsize);
i=ListEmpty(L); printf("L是否空；i=%d(1：是，0：否)\n",i); ClearList(L); i=ListEmpty(L);
printf("清空L后：L.elem=%u L.length=%d\nL.listsize=%d\n",L.elem,L.length,L.listsize); printf("L是否空：i=%d(1：是，0：否)\n",i);
for(j=1;j<=10;j++)
ListInsert(L,j,j); printf("在L的表尾依次插入1~10后：*L.elem="); for(j=1;j<=10;j++)
cout<<*(L.elem+j-1)<<" ";
cout<< printf("L.elem=%u L.length=%d L.listsize=%d \n",L.elem,L.length,L.listsize); ListInsert(L,1,0); printf("在表头插入0后：*L.elem="); for(j=1;j<=ListLength(L);j++)
cout<<*(L.elem+j-1)<<" ";
cout<< printf("L.elem=%u(有可能改变) L.length=%d(改变) L.listsize=%d(改变) \n",L.elem,L.length,L.listsize);
printf("请输入查找元素的位置i（0<i<12）："); scanf("%d",&i); GetElem(L,i,e); printf("第%d个值为：%d\n",i,e);
while(1) {
printf("请输入要查找的元素：");
scanf("%d",&j);
if((k=LocateElem(L,j,equal))==0)
printf("没有此元素！\n");
else } printf("第%d个元素的值为%d\n",k,j);
printf("测试前两个数据："); for(j=1;j<=2;j++) {
GetElem(L,j,e0);
i=PriorElem(L,e0,e);
printf("元素%d无前驱\n",e0);
printf("元素%d的前驱是%d\n",e0,e); }
printf("测试最后两个数据："); for(j=ListLength(L)-1;j<=ListLength(L);j++) {
GetElem(L,j,e0);
i=NextElem(L,e0,e);
printf("元素%d无后继\n",e0);
printf("元素%d的后继是%d\n",e0,e); } while(1) {
printf("请输入要删除的元素的位置：");
scanf("%d",&j);
if((i=ListDelete(L,j,e))==0)
printf("删除第%d个数据失败！\n",j);
else } printf("删除第%d个数据成功，其值为%d\n",j,e); printf("依次输出元素：");
ListTraverse(L,print); DestroyList(L);
printf("销毁L后：L.elem=%u L.length=%d\nL.listsize=%d\n",L.elem,L.length,L.listsize);}
为您推荐：
扫描下载二维码
