线性表的基本运算包括哪些 c语言数据表怎么做
线 性 表,线性表的基本操作:插入、删除、查找等运算在链式存储结构上的运算,线性表的操作,数据结构实验:线性表的顺序表示和链式表示及插入、删除、查找运算,数据结构线性表基本操作,线性表的基本操作c语言实现。
本文导航
线性表零基础
线性表是最基本、最简单、也是最常用的一种数据结构。线性表中数据元素之间的关系是一对一的关系,即除了第一个和最后一个数据元素之外,其它数据元素都是首尾相接的。线性表的逻辑结构简单,便于实现和操作。因此,线性表这种数据结构在实际应用中是广泛采用的一种数据结构。
线性表是一种常用的数据结构,本章介绍线性表及其顺序存储,并对栈和队列及它们的顺序实现给出了详细的设计描述。
在实际应用中,线性表都是以栈、队列、字符串、数组等特殊线性表的形式来使用的。由于这些特殊线性表都具有各自的特性,因此,掌握这些特殊线性表的特性,对于数据运算的可靠性和提高操作效率都是至关重要的。
线性表是一个线性结构,它是一个含有n≥0个结点的有限序列,对于其中的结点,有且仅有一个开始结点没有前驱但有一个后继结点,有且仅有一个终端结点没有后继但有一个前驱结点,其它的结点都有且仅有一个前驱和一个后继结点。一般地,一个线性表可以表示成一个线性序列:k1,k2,…,kn,其中k1是开始结点,kn是终端结点。
是一个数据元素的有序(次序)集
线性结构的基本特征为:
1.集合中必存在唯一的一个“第一元素”;
2.集合中必存在唯一的一个 “最后元素” ;
3.除最后一个元素之外,均有 唯一的后继(后件);
4.除第一个元素之外,均有 唯一的前驱(前件)。
由n(n≥0)个数据元素(结点)a1,a2,…,an组成的有限序列。
数据元素的个数n定义为表的长度。
当n=0时称为空表。
常常将非空的线性表(n>0)记作:
(a1,a2,…an)
数据元素ai(1≤i≤n)只是一个抽象的符号,其具体含义在不同的情况下可以不同。
线性表的基本操作
1)Setnull(L) 置空表
2)Length(L) 求表长度;求表中元素个数
3)Get(L,i) 取表中第i个元素(1≤i≤n)
4)Prior(L,i) 取i的前趋元素
5)Next(L,i) 取i的后继元素
6)Locate(L,x) 返回指定元素在表中的位置
7)Insert(L,i,x)插入元素
8)Delete(L,x) 删除元素
9)Empty(L) 判别表是否为空
线性表具有如下的结构特点:
1.均匀性:虽然不同数据表的数据元素可以是各种各样的,但对于同一线性表的各数据元素必定具有相同的数所类 长度。
2.有序性:各数据元素在线性表中的位置只取决于它们的序与,数据元素之前的相对位置是线性的,即存在唯一的“第一个“和“最后一个“的数据元素,除了第一个和最后一个外,其它元素前面均只有一个数据元素直接前趋和后面均只有一个数据元素(直接后继)。
在实现线性表数据元素的存储方面,一般可用顺序存储结构和链式存储结构两种方法。链式存储结构将在本网站线性链表中介绍,本章主要介绍用数组实现线性表数据元素的顺序存储及其应用。另外栈.队列和串也是线性表的特殊情况,又称为受限的线性结构。
线性表的两种存储结构
万恶的数据结构 你是几班的啊~~~我电信071~~~~
对线性表的总结和体会
我做的过的一个数据结构的课程设计的题目(以下是报告,代码可以运行的):也是用单链表做的,可以看一下,自己改下代码就好,原理都一样的…………
题目:约瑟夫问题的一种描述是:编号为1、2、3……n的n给人按瞬时针方向围坐一圈,每个人持有一个密码(正整数)。一开始任选一个正整数作为报数上限值m,从第一个人开始按顺时针方向自1开始顺序报数,报到m时停止报数。报m的人出列,将他的密码作为新的m值,从他在顺时针方向上的下一个人开始重新从1报数,如此下去,直至所有人全部出列为止。试设计一个程序求出出列顺序。
一、需求分析
1.利用单向循环链表存储结构模拟此过程,按照出列顺序印出个人的编号。
2.程序执行的命令包括:1)构造单向循环链表 2)求出出列的顺序
3.测试数据:m的出植为20;n=7,7个人的密码一次为:3,1,7,2,4,8,4,首先m植为6(正确的出列顺序应为6,1,4,7,2,3,5)。
二、概要设计
为实现上述程序功能,需创建一个循环单链表。
本程序包括四个模块:
1. 程序模块:
int main()
{调用intLinklist函数,建立链表L;
调用link_lit函数处理链表;}
2.建立链表模块:
输入m、n及n个密码,建立链表L,L指向尾结点。
3.链表处理表模块:
按要求处理链表L并输出出列顺序。
三、详细设计
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#define OVERFLOW -2
#define INFEASIBLE -1
#define ERROR O
int m,n;
typedef int ElemType; //元素类型
typedef struct LNode
{ElemType num;
ElemType pas;
LNode *next;
}LNode ,*Linklist; //结点类型、指针类型
void FreeNode(Linklist &p)
{ //释放p所指的结点
}
int intLinklist (Linklist &L)
{//创建循环单链表
printf("请输入报数的上限m:"); //输入m的值
scanf("%d",&m);
if(m<1) return INFEASIBLE;
int i,pas;
Linklist p,q;
printf("请输入人数n:");
scanf("%d",&n);
if(n<1) return INFEASIBLE;
L=p=(Linklist)malloc(sizeof(LNode));
if(!p)exit(OVERFLOW);
printf("请输入第个人的密码:");
p->num=1;
scanf("%d",& p->pas);
for(i=2;i<=n;i++)
{q=(Linklist)malloc(sizeof(LNode));
if(!q) exit(OVERFLOW);
p->next=q;
p=p->next;
printf("请输入第%d个人的密码:",i);
scanf("%d",&p->pas);
p->num=i;
}
p->next=L;
}
int link_list(Linklist &L,int &m) //链表处理
{
printf("出列的顺序为:\n");
Linklist r,s;
int j;
s=L;
while(s->next->next!=s)
{
if(m==1)
{r=s;
while(s->next!=r) //m=1时,查找r前面的一个结点,用指针s指向它
s=s->next;
printf("%d\n",r->num);
m=r->pas;
s->next=r->next;
s=s->next;
}
else
{for(j=1;j<m-1;j++)
s=s->next; //查找第m-1个结点,用s指针指向它
r=s->next; //r指针指向第m个结点
printf("%d\n",r->num);
m=r->pas;
s->next=r->next;
s=s->next;}
}
printf("%d\n",s->num); //当剩下两个结点时直接输出这两个结点的num值
printf("%d\n",s->next->num);
return 0;
}
int main()
{Linklist L;
intLinklist(L); //调用intLinklist函数,建立链表L
link_list(L,m); //调用link_lit函数处理链表
return 0;
}
四、调试分析
1. 开始时对循环单链表的建立考虑不足,程序不够简洁。
2. 原来的程序中将L指向链表的首元结点,当m=1时要查找最后一个结点,将L改为指向尾结点后就不需有考虑m=1的情况了。
3.原来的主函数因为有各个数据的输入而不够简洁,将m,n及各个密码的值的输入放到创建链表的函数中完成后,主函数比原来简洁易读得多,函数的调用一目了然。
五、测试结果
1.输入m值:20,n值:7,七个密码分别为:3、1、7、2、4、8、4
输出的结果为:6、1、4、7、2、3、5
2. 输入m值:1,n值:5,七个密码分别为:5、4、3、2、1
输出的结果为:1、2、3、4、5
数据结构中的顺序表是什么
#include<stdio.h>#include<stdlib.h>
typedef int ElemType;
/*构建结点结构体 */typedef struct LNode
{
int data;
struct LNode * next;
}LNode, * LinkList;
/*用于创建链表的函数 */
/*反序构建的*/
LinkList CreateList_L(LinkList L, int n)
{
int i;
LinkList p;
L = (LinkList)malloc(sizeof(LNode));
L->next = NULL;
for(i = 0; i < n; ++i)
{
p = (LinkList)malloc(sizeof(LNode));
scanf("%d",&p->data);
p->next = L->next;
L->next = p;
}
return L;
}
/*用于查找的函数*/LinkList GetElem_L(LinkList L,int i,ElemType &e)
{
LinkList p = L;
int j;
p = L->next;j = 1;
while(p && j<i)
{
p = p->next;
++j;
}
if(!p || j>i)
{
printf("表中无此位置。\n");
return L;
}
e = p->data;
printf("%d\n",e);
return L;
}
/* 用于插入结点的函数 */LinkList ListInsert_L(LinkList L, int i, int newnode)
{
LinkList p = L;
LinkList s;
int j = 0;
while(p&&j<i-1)
{
p = p->next;
++j;
}
if(!p||j>i-1)
{
printf("位置小于1或大于表长。\n");
return L;
}
s = (LinkList)malloc(sizeof(LNode));
s->data = newnode;
s->next = p->next;
p->next = s;
return L;
}
/* 用于删除结点的函数 */LinkList ListDelete_L(LinkList L, int i)
{
LinkList p = L;
LinkList s;
int j=0;
while(p->next&&j<i-1)
{
p = p->next;
++j;
}
if(!(p->next)||j>i-1)
{
printf("删除位置不合理。\n");
return L;
}
s = p->next;
p->next = s->next;
printf("%s%d\n","被删除的结点是:",s->data);
free(s);
return L;
}
/*用于遍历链表的函数 */
void ListDisp_L(LinkList L)
{
LinkList p;
int i=0;
p = L->next;
while(p)
{
printf("%d:%d\n", ++i,p->data);
p = p->next;
}
}
int main(){
int where;
int value;
int count;
int search;
int output;
LinkList L; printf("请输入链表初始结点数:");
scanf("%d",&count);
printf("请输入各个结点数值,每输入一个按回车确认:\n");
L = CreateList_L(L, count);
printf("请输入要查找的位置:");
scanf("%d",&search);
L = GetElem_L(L,search,output);
printf("请输入插入的位置:");
scanf("%d", &where);
printf("请输入要插入的数值:");
scanf("%d", &value);
L = ListInsert_L(L,where,value);
ListDisp_L(L);
printf("请输入要删除的位置:"); scanf("%d",&where);
L = ListDelete_L(L,where);
ListDisp_L(L);
return 0;
}
数据结构链表图解
#include <iostream>
#include <cstdio>
#include <cstdlib>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
using namespace std;
typedef int Elemtype;
typedef struct
{
Elemtype *elem;
int length;
int listsize;
} SqList;
int InitList_Sq(SqList &L)//L在下面发生变化,故用引用
//构造一个新的线性表
{
L.elem=(Elemtype *)malloc(LIST_INIT_SIZE*sizeof(Elemtype));
if(!L.elem)
exit(OVERFLOW);
L.length=0;//空表长度为0
L.listsize=LIST_INIT_SIZE;//初始存储容量
return OK;
}
int ListInsert_Sq(SqList &L,int i,Elemtype e)
//在顺序表L中的第i个位置插入新的元素e
//i的合法值为1<=i<=ListLength_Sq(L)+1
{
Elemtype * newbase;
Elemtype* p;
Elemtype* q;
if(i<1||i>L.length+1)//判断i值是否合法
return ERROR;
if(L.length>=L.listsize)//增加分配空间
{
newbase=(Elemtype*)realloc(L.elem,
(L.listsize+LISTINCREMENT)*sizeof(Elemtype));
if(!newbase)//存储分配失败
exit(OVERFLOW);
L.elem=newbase;//新基址
L.listsize+=LISTINCREMENT;//增加存储容量
}
/*for(int j=L.length;j>=i;j--)//元素右移
L.elem[j+1]=L.elem[j];
L.elem[i]=e;//插入e
L.length++;//表长增加
return OK;*/
q=&(L.elem[i-1]);//指针操作
for(p=&(L.elem[L.length-1]); p>=q; --p)
{
*(p+1)=*p;
}
*q=e;
++L.length;
return OK;
}
int main()
{
int i,n,x,k;
SqList La;
cout<<"请输入线性表La的长度:";
cin>>n;
cout<<"请输入线性表La中的元素:";
InitList_Sq(La);
for(i=0; i<n; i++)
{
cin>>La.elem[i];
La.length++; //如果不加这句,你要让La.length=n;
}
cout<<"请输入要插入到线性表La中的数字x和插入的位置k:";
cin>>x>>k;
ListInsert_Sq(La,k,x);
cout<<"线性表La=";
for(i=0; i<La.length; i++)//你的是i<n你插入元素的时候n没有变,不,
cout<<La.elem[i]<<" ";
return 0;
}
你自己看看
c语言数据表怎么做
代码如下:
头文件:
2_1.h
#ifndef; _2_1_H
#define; _2_1_H
typedef void SeqList;
typedef void SeqListNode;
//创建线性表
SeqList * SeqList_Create(int capacity);
//销毁线性表
void SeqList_DesTroy(SeqList * list);
void SeqList_Clear(SeqList* list);
int SeqList_Length(SeqList* list);
int SeqList_Capacity(SeqList* list);
int SeqList_Insert(SeqList* list, SeqListNode* node, int pos);
SeqListNode* SeqList_Get(SeqList* list, int pos);
SeqListNode* SeqList_Delete(SeqList* list, int pos);
#endif
源文件:
// 顺序线性表.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include <malloc.h>
#include <stdlib.h>
#include "2_1.h"
typedef unsigned int TSeqListNode;
typedef struct {
int len;; ; ;//长度
int capacity;//总长度
TSeqListNode * node;//每个节点的指针
} TSeqList;
int main()
{
SeqList* list = SeqList_Create(5);//创建线性表
int i = 6;//赋值6个变量,已超过线性表最大值 5
int j = 1;
int k = 2;
int x = 3;
int y = 4;
int z = 5;
int index = 0;
SeqList_Insert(list, &i, 7); //将这6个变量插入线性表中
SeqList_Insert(list, &j, 0);
SeqList_Insert(list, &k, 0);
SeqList_Insert(list, &x, 0);
SeqList_Insert(list, &y, 0);
SeqList_Insert(list, &z, 0);
//遍历
for(index=0; index<SeqList_Length(list); index++)
{
int* p = (int*)SeqList_Get(list, index);
printf("%d; ", *p);
}
printf("\n");
//删除操作
while( SeqList_Length(list) > 0 )
{
int* p = (int*)SeqList_Delete(list, 0);
printf("删除了: %d\n", *p);
}
SeqList_Clear(list);
SeqList_DesTroy(list);
system("pause");
return 0;
}
//创建线性表
SeqList * SeqList_Create(int capacity)
{
TSeqList* ret = NULL ;
if(capacity >= 0)
{
ret = (TSeqList*)malloc(sizeof(TSeqList) + sizeof(TSeqListNode)*capacity);; //为线性表分配空间,包含结 //构体和节点的总大小
}
if(NULL != ret)
{
ret->len = 0;
ret->capacity = capacity;
ret->node = (TSeqListNode*)(ret + 1);//将节点指向上述分配到的空间的后部分
}
return ret;
}
//销毁
void SeqList_DesTroy(SeqList * list)
{
free(list);
}
//清空
void SeqList_Clear(SeqList* list)
{
TSeqList * ret = (TSeqList*)list;
if(NULL != ret)
{
ret->len = 0;
}
}
//获得线性表的长度
int SeqList_Length(SeqList* list)
{
TSeqList * ret = (TSeqList*)list;
int len = -1;
if(NULL != ret)
{
len = ret->len;
}
return len;
}
//线性表的总长度
int SeqList_Capacity(SeqList* list)
{
TSeqList * ret = (TSeqList*)list;
int capacity = -1;
if(NULL != ret)
{
ret->capacity = capacity;
}
return capacity;
}
//插入
int SeqList_Insert(SeqList* list, SeqListNode* node, int pos)
{
TSeqList * sList = (TSeqList*)list;
int i,ret = -1;
if((sList != NULL) &&(pos >= 0) && sList->capacity >= sList->len+1)
{
if(pos >= sList->len)
{
pos = sList->len;
}
for(i = sList->len; i > pos; i--)
{
sList->node[i] = sList->node[i-1];
}
sList->node[i] = (TSeqListNode)node;
++sList->len;
ret = 1;
}
return ret;
}
//获得指定位置的节点
SeqListNode* SeqList_Get(SeqList* list, int pos)
{
TSeqList * sList = (TSeqList*)list;
TSeqListNode* node = NULL;
if(NULL != sList && pos>=0 && pos < sList->len)
{
node = (TSeqListNode*)sList->node[pos];
}
return node;
}
//删除
SeqListNode* SeqList_Delete(SeqList* list, int pos)
{
TSeqList * sList = (TSeqList*)list;
SeqListNode * node = SeqList_Get( list, pos);
int i;
if(sList != NULL && pos >= 0 && pos< sList->len)
{
for( i=pos+1; i<sList->len; i++)
{
sList->node[i-1] = sList->node[i];
}
sList->len--;
}
return node;
}
演示:
资料拓展:
线性表是最基本、最简单、也是最常用的一种数据结构。
线性表中数据元素之间的关系是一对一的关系,即除了第一个和最后一个数据元素之外,其它数据元素都是首尾相接的(注意,这句话只适用大部分线性表,而不是全部。比如,循环链表逻辑层次上也是一种线性表(存储层次上属于链式存储),但是把最后一个数据元素的尾指针指向了首位结点)。
我们说“线性”和“非线性”,只在逻辑层次上讨论,而不考虑存储层次,所以双向链表和循环链表依旧是线性表。
在数据结构逻辑层次上细分,线性表可分为一般线性表和受限线性表。一般线性表也就是我们通常所说的“线性表”,可以自由的删除或添加结点。受限线性表主要包括栈和队列,受限表示对结点的操作受限制。
线性表的逻辑结构简单,便于实现和操作。因此,线性表这种数据结构在实际应用中是广泛采用的一种数据结构。