java中的接口是类吗
488
2022-08-27
线性表(线性表出的系数可以全为0吗)
顺序存储的定义:线性表的顺序存储结构,指的是用一段地址连续的存储单元依次存储线性表的数据元素。
C语言中一维数组的实现就是一种顺序存储结构。
/** ADT (List) Data 线性表的数据对象集合为{a1,a2,....,an},每个元素的类型均为DataType.其中,除了第一个元素a1外,每个元素有且只有一个直接的前驱元素 同理,除了最后一个元素an外,每一个元素有且仅有一个直接的后继元素,数据元素之间是一对一的关系。 Operation InitList(*L); // 初始化操作,建立一个空的线性表. ListEmpty(L); // 若线性表为空,则返回true,否则返回false. ClearList(*L); // 将线性表清空. GetElem(L,i,*e); // 将线性表L中的第i个元素值返回给e. LocateElem(L,e); // 在线性表L中查找与给定的值e相等的元素,如果查找成功则返回该元素在表中的序列号;否则返回0,表示失败. ListInsert(*L,i,e); // 在线性表L中的第i个位置插入新元素e. ListDelete(*L,i,*e); // 删除线性表L中第i个位置的元素,并用元素e返回其值. ListLength(L); // 返回线性表元素的个数. endADT**/
下面是线性表顺序存储的结构代码:
/*方式一*/#define MAXSIZE 10 //初始分配量typedef int Elemtype;//这里比较灵活,一般是可以char,int,float这些原子类型的数据typedef struct { Elemtype r[MAXSIZE];//最大的存储量:数据长度(数据长度),在宏定义之后一般是不变的,以非指针的形式说明 int length; //当前长度<=MAXSIZE,线性表长度是可变的,由于增删的缘故}Sqlist;//这一种比较好理解,但是实际写代码时会遇到L.r=a(表达式必须是可修改的左值)//报错原因由于r[MAXSIZE]中r时数组名不是指针,不可修改,是一个分配在.bss段的确定的地址/*方式二,更加灵活,应用指针*/#define MAXSIZE 10typedef int ELemtype;typedef struct { Elemtype *r; int length; int size;//没错我们可以优化结构体,将r[MAXSIZE]拆成指针和一个int的原子数据类型,初始化是会很方便}//这是我的数据结构书上的//当然,如果考虑到SqlistInit()这样的函数引入,利用循环结构也可以达到同样的目的,但那会更麻烦/* *区分数据长度和线性表长度,数据长度一般不变,线性表长度受限于实际的元素个数 *顺序存储由于对地址LOC(ai)=LOC(a0)+sizeof(Elemtype)*i,所以时间复杂度为O(1) *具有LOC这样的特点的结构称之为随机存储结构(比如数组) */
顺序存储结构
注意区分:线性表的长度与数组的长度
获取元素
3.5.1 线性表获取元素
#define OK 1#define ERROR 0typedef int Status; // show the status of function Status GetElem(SqList *L,int i,ElemType *e){ /*check the value of i */ if (i > 0 && i < L->length && L->length != 0) // ensure the Sqlist is not Null *e = L->data[i]; return OK; else printf("can't find the value"); return ERROR;}
插入元素
3.5.2 插入算法的注意事项:
插入位置不合适,抛出异常(异常处理)L->length > L->size,则需要动态的扩容或者抛出异常倒序遍历后移一位元素对应插入到第i个位置L->length += 1
#define OK 1#define ERROR 0typedef int Status; // show the status of functionStatus InsertElem(Sqlist *L,int i,Elemtype e){ if (i > L->length || i < 1) // ensure the index is normal return ERROR; else if (L->length >= L->size)// justify the room enough return ERROR; else { for(int j = L->length;j > i; j--)// move elements L->data[j] = L->data[j-1] L->data[i] = e; // j的作用域随着for循环结束而结束 }}
链表
链表节点
typedef struct Node{ Elemtype data; struct Node * next;//下一个节点的地址}Node;typedef struct Node *Linklist ; //Linklist 是一种指针,指向节点类型
线性表与链表获取元素
GetElem()
//获取线性表对应位置的元素#include"stdio.h"#define OK 1#define ERROR 0#define True 1#define Faulse 0typedef int Status;//Status 返回函数的状态码,说明函数的执行情况/* *int GetElem( Sqlist * L,Elemtype e),返回位置 *获取元素的前提是线性表已经存在,习惯上由于返回位置非0,即0是元素不在线性表中 *要求1=length(即i有意义),操作结果:返回对应位置的元素的值 */#define MAXSIZE 10 //指定数组的容量,即数据长度typedef int Elemtype;typedef struct { Elemtype * r; int length;//说明线性表的长度 int size;}Sqlist;int main();Status GetElem(Sqlist *L,int i,Elemtype *e);//返回这里做了优化处理,原来的int 成为状态码,返回值int main(){Sqlist L;int loc;int a[MAXSIZE]={1,2,3,4,5,7,6,8,9,10};L.r=a; //r在这里指针,可以修改L.length=MAXSIZE;Elemtype ch;GetElem(&L,7,&ch);printf("第七个元素是:%d",ch);return 0;}Status GetElem(Sqlist *L,int i,Elemtype* e){ if(i<1||i>L->length)//比较的时候比的是实际的线性表长度 return ERROR; else { *e=L->r[i-1]; return OK; } }
//单链表的读取:GetElem()/*单链表的定位一开始是相对复杂的,有点类似树中的遍历 *操作目的:获取单链表第i个元素都数据域的值 * L->next就是a1,以此类推,须注意的是循环条件 * 涉及二级指针 */#include"stdio.h" //没有文件的包含报未定义标识符"NULL"的错误#include"malloc.h"#define MAXSIZE 10#define OK 0#define ERROR 1typedef int Status;typedef int Elemtype;typedef struct Node{ Elemtype r; struct Node * next;}Node;typedef Node * LinkList;//一级指针int main();Status LinkListInit(Node** L,int *a);void GetElem(LinkList L,int i,int *e);int main(){ Elemtype e; LinkList L; int a[MAXSIZE]={1,2,3,4,5,6,7,8,9,0}; LinkListInit(&L,a);//指针更新,这种写法没法改变L的值,可以知道L为指针,我们的目的是修改是修改指针 GetElem(L,6,&e); printf("%d ",e); }Status LinkListInit(Node** L,int *a)//二级指针真香{ Node *p;//这里使用LinkList的话报必须使用指向结构的类型 p=(Node *)malloc(sizeof(Node));//头结点申请 *L=p;//记录执行头指针的p,赋值给L; if(!p) return ERROR;//头结点申请失败 for(int i=0;i<=9;i++) { p->next=(Node *)malloc(sizeof(Node)); p->r=a[i]; p=p->next; } p->next=NULL; return 0;}void GetElem(LinkList L,int i,int *e){ Node * p; p=L; int j=1; while(p&&j<=i-1) { p=p->next; j++; } *e=p->r;}
链表插入节点
InsertElem()
/** ADT (List) Data 线性表的数据对象集合为{a1,a2,....,an},每个元素的类型均为DataType.其中,除了第一个元素a1外,每个元素有且只有一个直接的前驱元素 同理,除了最后一个元素an外,每一个元素有且仅有一个直接的后继元素,数据元素之间是一对一的关系。 Operation InitList(*L); // 初始化操作,建立一个空的线性表. ListEmpty(L); // 若线性表为空,则返回true,否则返回false. ClearList(*L); // 将线性表清空. GetElem(L,i,*e); // 将线性表L中的第i个元素值返回给e. LocateElem(L,e); // 在线性表L中查找与给定的值e相等的元素,如果查找成功则返回该元素在表中的序列号;否则返回0,表示失败. ListInsert(*L,i,e); // 在线性表L中的第i个位置插入新元素e. ListDelete(*L,i,*e); // 删除线性表L中第i个位置的元素,并用元素e返回其值. ListLength(L); // 返回线性表元素的个数. endADT**//*目标:将所有的在线性表Lb中的但是不在线性表La的数据元素插入La中*/
#include"stdio.h" //没有文件的包含报未定义标识符"NULL"的错误#include"malloc.h"#define MAXSIZE 10#define OK 0#define ERROR 1typedef int Status;typedef int Elemtype;typedef struct Node{ Elemtype r; struct Node * next;}Node;typedef Node * LinkList;//一级指针int main();Status LinkListInit(Node** L,int *a);Status ElemInsert(LinkList* L,int i,Elemtype e);void ElemPrint(Node** L);int main(){ Elemtype e; LinkList L; int a[MAXSIZE]={1,2,3,4,5,6,7,8,9,0}; LinkListInit(&L,a);//指针更新,可以知道L为指针,我们的目的是可以修改一级指针 ElemInsert(&L,2,11); ElemPrint(&L); }Status LinkListInit(Node** L,int *a)//二级指针真香{ Node *p;//这里使用LinkList的话必须使用指向结构的类型 p=(Node *)malloc(sizeof(Node));//头结点申请 *L=p;//记录执行头指针的p,赋值给L; if(!p) return ERROR;//头结点申请失败 for(int i=0;i<=9;i++) { p->next=(Node *)malloc(sizeof(Node)); p->next->r=a[i]; p=p->next; } p->next=NULL; return 0;}// if have head NodeStatus ElemInsert(Node**L,int i,Elemtype e){ Node *p = *L; int j = 1; while(p&&jnext; //the Node of j ++j; //j } if(!p || j > i) return ERROR; Node *new = (Node*)malloc(sizeof(Node)); new->r = e; new->next = p->next; // j+1 = i p->next = new; return OK; }void ElemPrint(Node** L){ Node *p = *L; while(p->next) { printf("%d ",p->next->r); p = p->next; }}
Q&A:
执行while之前,申请的链表之间顺次链接,从外界传入i是2,p一开始是头结点,L是头指针
当j=2时,插入节点会被放到第二个节点后面
p->r在末节点处非法读出,报segment错误
头结点的数据域被写入的,引发异常
删除节点
Status NodeDelete(LinkList *L,int i,Elemtype *e){ Node *p = *L; int j = 1; while(p->next && j < i) //aj { p = p->next; ++j; } if(!(p->next)||j > i) return ERROR; Node *q = p->next;//q is the Node of i p->next = q->next; *e = q->r; free(q); return OK;}
单链表的创建
Status LinkListInit(Node** L,int *a)//二级指针真香{ Node *p;//这里使用LinkList的话必须使用指向结构的类型 p=(Node *)malloc(sizeof(Node));//头结点申请 *L=p;//记录执行头指针的p,赋值给L; if(!p) return ERROR;//头结点申请失败 for(int i=0;i<=9;i++) { p->next=(Node *)malloc(sizeof(Node)); p->next->r=a[i]; p=p->next; } p->next=NULL; // 尾指针域置空 return 0;}
静态链表
用数组描述的链表叫做静态链表,也称为游标实现法。
#include"stdio.h" #include"malloc.h"#define MAXSIZE 1000#define OK 0#define ERROR 1typedef int Status;typedef int Elemtype;typedef struct { Elemtype data; int cur;}Node,StaticLinkList[MAXSIZE];// StaticLinkList is ptrint main();Status InitStaticLinkList(StaticLinkList L);Status ElemInsert(LinkList* L,int i,Elemtype e);void ElemPrint(Node** L);Status InitStaticLinkList(StaticLinkList L){ int i; for(i=0; i 静态链表的插入与删除 #include"stdio.h" #define MAXSIZE 1000#define OK 0#define ERROR 1typedef int Status;typedef int Elemtype;typedef struct { Elemtype data; int cur;}Component,StaticLinkList[MAXSIZE];// StaticLinkList is ptr point tp Component [MAXSIZE]//typedef StaticLinkList SLL;typedef Component *SSL;int main();int Malloc_SSL(StaticLinkList L);void Free_SSL(StaticLinkList L,int k);int ListLength(StaticLinkList L);Status InitStaticLinkList(StaticLinkList L);Status ElemInsert(StaticLinkList L,int i,Elemtype e);Status ElemDelete(StaticLinkList L,int i);void ElemPrint(StaticLinkList L);int Malloc_SSL(StaticLinkList L){ int next = L[0].cur; // the current Null if(L[0].cur) L[0].cur = L[next].cur; // the next Null return next;}void Free_SSL(StaticLinkList L,int k){ L[k].cur = L[0].cur; L[0].cur = k; // like BIN in malloc & free}int ListLength(StaticLinkList L){ int i = 0 ; // the last elem cur is Null int cursor = L[MAXSIZE-1].cur; while(cursor) { cursor = L[cursor].cur; i++; } return i;}Status InitStaticLinkList(StaticLinkList L){ int i; for(i=0; i gdb 调试的时候发现一个局部变量在Malloc_SSL函数中出错,导致没有输出。
版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。
发表评论
暂时没有评论,来抢沙发吧~