线性表(数据结构期末复习4)
顺序表的基础操作
存储结构定义增删改查和有序数组的合并。注意pos 不是 index。realloc的使用。
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#define TRUE 1
#define False 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define LIST_INIT_SIZE 100
#define LISTINCREAMENT 10
typedef int Status;//Status是一种int的数据类型
typedef int ELemtype;//Elemtype 是一种int的数据类型
typedef struct
{
//数组指针存数
//数组长度
//数组容量
ELemtype *elem;
int length;
int listsize;
}Sqlist;//定义结构体名称
Status Initlist_Sq(Sqlist &L)
{
//申请空间
L.elem=(ELemtype*)malloc(sizeof(ELemtype)*LIST_INIT_SIZE);
//申请失败了就exit
if(!L.elem)
exit(OVERFLOW);
//初始化容量和长度
L.listsize=LIST_INIT_SIZE;
L.length=0;
return OK;
}
Status ListInsert(Sqlist &L,int pos,ELemtype e)
{
if(pos<0||pos>L.length+1)//只要插入的位置不在 1~L.length+1的范围里面
return ERROR;
if(L.length+1>L.listsize)//如果插入之后超过容量就扩展容量
{
L.elem=(ELemtype*)realloc(sizeof(ELemtype)*(L.listsize+LISTINCREAMENT));
if(!elem)
exit(OVERFLOW);
L.listsize+=10;
}
//插入就是一直后移,把当前位置和之后的都向后移动
ELemtype *p;
p=elem+L.length-1;//让指针指向数组的最后一个位置
while(p>=elem+pos-1)
{
*(p+1)=*p;
p--;
}
*(p++)=e;//当前位置前面位置现在已经是空了
L.length++;
return OK;
}
Status ListDelect_Sq(Sqlist &L,int pos,ELemtype &e)
{
if(pos<1||pos>L.length)//删除的位置和插入的位置不一样
return ERROR;
ELemtype* p=L.elem+pos-1;
e=*p;
while(p<L.elem+L.length)//是把后面的每一个元素都向前移动一位
{
*(p-1)=*p;
p++;
}
L.length--;
return OK;
}
int ListLocate_Sq(Sqlist L,ELemtype e)
{
Elemtype *p=L.elem;
while(p<L.elem+L.length)
{
if(*p==e)
break;
p++;
}
int pos=p-L.elem+1;
return pos;
}
Status ListMerge_SortedSq(Sqlist La,Sqlist Lb,Sqlist &Lc)
{
if(Lc.listsize<La.length+Lb.length)
{
Lc.elem=(ELemtype*)malloc(sizeof(ELemtype)*(La.length+Lb.length));
Lc.length=La.length+Lb.length;
}
int i=0,j=0;k=0;
while(i<La.length&&j<Lb.length)
{
if(La.elem[i]<Lb.elem[j])
{
Lc.elem[k++]=La.elem[i++];
}
else
{
Lc.elem[k++]=Lb.elem[j++];
}
Lc.length++;
}
while(i<La.length)
{
Lc.elem[k++]=La.elem[i++];
Lc.length++;
}
while(j<Lb.length)
{
Lc.elem[k++]=Lb.elem[j++];
Lc.length++;
}
return OK;
}
链表的基础操作
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#define TRUE 1
#define False 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;//Status是一种int的数据类型
typedef int ELemtype;//Elemtype 是一种int的数据类型
typedef struct LNode
{
//结点的数据
//结点指向的下一个结点
ELemtype data;
struct LNode* next;
}LNode,*LinkList;//定义结构体名称,指针名称。
Status ListCreate_L(LinkList &L,int n)
{
//先给L开辟空间,然后再一次记录尾结点和当前结点进行链表的延伸
LNode *rearptr,*curptr;
L=(LNode*)malloc(sizeof(LNode));
if(!L)
exit(OVERFLOW);
L->next=NULL;
scanf("%d",L->data);//先初始化一个结点
rearptr=L;//让尾指针指向当前结点
for(int i=1;i<n;i++)
{
curptr=(LNode*)malloc(sizeof(LNode));
curptr->next=NULL;
scanf("%d",curptr->data);
rearptr->next=curptr;
rearptr=curptr;
}
return OK;
}
Status ListCreate_L2(LinkList &L,int n)//头插法
{
//还是先给L开辟空间,但是这个L不存数,使用头插法构成链表。
L=(LNode*)malloc(sizeof(LNode));
L->next=NULL
LNode *curptr=NULL;
for(int i=0;i<n;i++)
{
curptr=(LNode*)malloc(sizeof(LNode));
scanf("%d",&curptr->data);
curptr->next=L->next;
L->next=curptr;
}
return OK;
}
Status Insert_LN(LinkList &L,int pos,ELemtype e)
{
LinkList p=L,q=NULL;
if(pos<1)
return ERROR;
int cnt=0;
while(p&&cnt<pos-1)//链表的操作是找到要插入位置之前的结点
{
p=p->next;
}
if(!p)
return ERROR;
q=(LNode*)malloc(sizeof(LNode));
q->next=p->next;
q->data=e;
p->next=q;
return OK;
}
Status Delete_LN(LinkList &L,int pos , ELemtype &e)
{
LinkList p=L;
int cnt=0;
while(p&&cnt<pos-1)//找到从0开始到pos-2(就是要删除的位置的前一个)
{
p=p->next;
}
if(!p)
return ERROR;
else
{
LinkList q=p->next;//释放掉
e=q->data
free(q);
q=NULL;
}
return OK;
}
Status ListInsert(Sqlist &L,int pos,ELemtype e)
{
if(pos<0||pos>L.length+1)//只要插入的位置不在 1~L.length+1的范围里面
return ERROR;
if(L.length+1>L.listsize)//如果插入之后超过容量就扩展容量
{
L.elem=(ELemtype*)realloc(sizeof(ELemtype)*(L.listsize+LISTINCREAMENT));
if(!elem)
exit(OVERFLOW);
L.listsize+=10;
}
//插入就是一直后移,把当前位置和之后的都向后移动
ELemtype *p;
p=elem+L.length-1;//让指针指向数组的最后一个位置
while(p>=elem+pos-1)
{
*(p+1)=*p;
p--;
}
*(p++)=e;//当前位置前面位置现在已经是空了
L.length++;
return OK;
}
Status ListDelect_Sq(Sqlist &L,int pos,ELemtype &e)
{
if(pos<1||pos>L.length)//删除的位置和插入的位置不一样
return ERROR;
ELemtype* p=L.elem+pos-1;
e=*p;
while(p<L.elem+L.length)//是把后面的每一个元素都向前移动一位
{
*(p-1)=*p;
p++;
}
L.length--;
return OK;
}
int ListLocate_Sq(Sqlist L,ELemtype e)
{
Elemtype *p=L.elem;
while(p<L.elem+L.length)
{
if(*p==e)
break;
p++;
}
int pos=p-L.elem+1;
return pos;
}
Status ListMerge_SortedSq(Sqlist La,Sqlist Lb,Sqlist &Lc)
{
if(Lc.listsize<La.length+Lb.length)
{
Lc.elem=(ELemtype*)malloc(sizeof(ELemtype)*(La.length+Lb.length));
Lc.length=La.length+Lb.length;
}
int i=0,j=0;k=0;
while(i<La.length&&j<Lb.length)
{
if(La.elem[i]<Lb.elem[j])
{
Lc.elem[k++]=La.elem[i++];
}
else
{
Lc.elem[k++]=Lb.elem[j++];
}
Lc.length++;
}
while(i<La.length)
{
Lc.elem[k++]=La.elem[i++];
Lc.length++;
}
while(j<Lb.length)
{
Lc.elem[k++]=Lb.elem[j++];
Lc.length++;
}
return OK;
}
双向链表和双向循环链表的插入和删除
//双向链表*/
#include<bits/stdc++.h>
using namespace std;
#define OK 1
#define ERROR -1
#define OVERFLOW -2
typedef int Status;
typedef int QElemtype;
typedef struct QNode
{
QElemtype data;
struct QNode* pre;
struct QNode* next;
}QNode,*LinkQueue;
//创建一个链表
Status Init_Queue(LinkQueue &Q)
{
//双向队列
Q=(QNode*)malloc(sizeof(QNode));
if(!Q)
exit(OVERFLOW);
Q->next=Q->pre=NULL;
return OK;
//双向循环队列
/*Q->next=Q;
Q->pre=Q;
return OK;*/
}
//插入数据(头插法)
//循环链表用尾插比较方便
Status Insert_Queue(LinkQueue &Q,QElemtype e)
{
LinkQueue p=(QNode*)malloc(sizeof(QNode));
p->data=e;
p->next=Q->next;
p->pre=Q;
Q->next->pre=p;
Q->next=p;
return OK;
}
//双向循环链表的尾插法
Status Insert_Queue2(LinkQueue &Q,QElemtype e)
{
LinkQueue p=(LinkQueue)malloc(sizeof(QNode));
if(!p)
exit(OVERFLOW);
p->next=Q;
p->pre=Q->pre;
Q->pre->next=p;
Q->pre=p;
return OK;
}
//链表节点的删除
Status Delete_Queue(LinkQueue &Q,int pos,QElemtype &e)
{
LinkQueue p=Q;
for(int i=0;i<n-1;i++)
{
p=p->next;
}
LinkQueue q=p->next;
p->next=q->next;
q->next->pre=p;
free(q);
q=NULL;
}
判断题:
1. int (*p)[4]它表示p是一个指针数组,它包含4个指针变量元素。
[ ]的优先级比 * 高,int *p[4] :意思是一个叫p的数组,以int * 为元素
int (*p)[4]: 先和 * 结合,说明是一个指针,指向 int[4],是一个n行4列的二维数组。
2. 数组指针,和指针数组
int* p[4]是指针数组。数组的元素是指针
int(*p)[4]是数组指针,是一个指向数组的指针。其实可以写成 int[4](*p)
补充:int a[4] ,p=a这样不行。p=&a这样可以,p相当于一个行指针。
3.结构体类型本身不占用内存空间,结构体变量占用内存空间。
4.设h
为不带头结点的单向链表。在h
的头上插入一个新结点t
的语句是:
t->next=h; h=t;
5.
线性表L在什么情况下适用于使用链式结构实现:.
需不断对L进行删除插入
6
. int c, *s, a[]={1, 3, 5};下列操作错误的是()
A.c=*s;
B. s[0]=a[0]; *s没有初始化,若是静态变量,s初始化为0,对地址为0的操作没有意义
C.s=&a[1];
D.c=a;
7.
(p->n)++ 和++p->n 相同 。->优先级高于++
8.定义结构体的几种类型
9.
数据的逻辑结构是指数据的各数据项之间的逻辑关系。F
是数据元素之间的逻辑关系,而不是数据元素的数据项之间的关系
10.
抽象数据类型中基本操作的定义与具体实现有关。F
数据类型先定义抽象的基本操作,然后再具体实现。具体实现各种各样。
11.数据的(逻辑结构)包括集合、线性结构、树形结构和图形结构四种基本类型。
12.数据结构是一门研究非数值计算的程序设计问题中计算机的(操作对象)以及它们之间的关系和运算等的学科。
13.在决定选取何种存储结构时,一般不考虑(各个结点的值如何)。
14,物理存储上可以把数据结构分为:顺序结构,链式结构
15. 在逻辑上可以把数据结构分为线性结构,非线性结构
16. 数据的最小单位是数据项,数据的基本单位是数据元素
17.while( x≥(y+1)*(y+1) ) {y++;}时间复杂度是 O(n1/2)
18.计算机算法指的是(解决问题的有限运算序列)。
19.计算机算法必须具备输入,输出和(可行性,确定性,有穷性)
20.对于顺序存储的长度为N的线性表,访问结点和增加结点的时间复杂度分别对应为O(1)和O(N)。T
增加结点需要移动大量数据
21.对于顺序存储的长度为N的线性表,删除第一个元素和插入最后一个元素的时间复杂度分别对应为O(1)和O(N)。F
对于线性表对最后一个元素的操作可以根据头地址加偏移量
22.顺序表中逻辑相邻的数据元素的物理位置是相邻的。
23.等差数列Sn=n*a1+n(n-1)d/2或Sn=n(a1+an)/2
线性表L=(a1, a2 ,……,an )用一维数组表示,假定删除线性表中任一元素的概率相同(都为1/n),则删除一个元素平均需要移动元素的个数是((n-1)/2)。
24. 带头结点的单链表h
为空的判定条件是:h->next == NULL;
25. 将长度为n的单链表连接在长度为m的单链表之后的算法的时间复杂度为(O(m) )。
26.可以用带表头附加结点的链表表示线性表,也可以用不带头结点的链表表示线性表,前者最主要的好处是(使空表和非空表的处理统一)。