数据结构考研笔记第二章

数据结构考研笔记第二章

木来 木来

1.   线性结构的特点:
存在唯一的“第一个”数据元素
存在唯一的“最后一个”数据元素
除第一个元素外,每个元素只有一个直接前驱
除最后一个元素外,每个元素只有一个直接后继

2.   用一组地址连续的存储单元依次存储线性表的数据元素。这样的线性表叫顺序表。

3.   线性表的顺序存储结构
#define LIST_INIT_SIZE 100
#define LISTINCREAMENT 10
typedef struct{
ElemType  *elem;
int length;
int listsize;
}SqList;

4.   初始化线性表
Status List_Init(SqList &L){
L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
if(!L.elem) exit(overflow);
L.length=0;
L.listsize=LIST_INIT_SIZE;
return ok;
}

5.   线性表的插入操作:
Status List_Insert(SqList &L,int I,ElemType e){
if(i<1||i>L.length+1) return ERROR;
if(L.length>=L.listsize){
newbase=(ElemType *) realloc((List.listsize+LISTINCREMENT
)*sizeof(ElemType));
if(!newbase) exit(overflow);
L.elem=newbase;
L.listsize+=LISTINCREMENT;
}
q=&(L.elem[i-1]);
for(p=&L.elem[L.length-1];p>=q;--p){
*(p+1)=*p;
}
*q=e;
++L.length;
return OK;
}

6.   线性表的删除:
Status List_Delete_sq(SqList &L,int i,ElemType &e){
if(i<1||i>L.length) return ERROR;
p=&L.elem[i-1];
e=*p;
q=&L.elem[L.length-1];
for(++p;p<=q;++p){
*(p-1)=*p;
}
--L.length;
return OK;
}

7.   线性表顺序存储结构的优点:查询方便,可以随机存取任意位置的元素,可以直接获取到线性表的长度
缺点:插入与删除不方便麻烦

8.   结点中只包括一个指针域的链表,叫做单链表

9.   头指针是指向链表中的第一个结点的指针。
单链表可由一个头指针唯一确定。

10. 头结点是在链表的首元结点之前附设的一个结点。数据域内只存放空表标志和表长等信息

11. 首元结点是链表中存储线性表的第一个数据元素的结点

12. 线性表的单链表存储结构:
typedef struct LNode{
ElemType data;
struct LNode  *next;
}LNode,*LinkList;

13. 在数据元素第i个位置之前插入新的结点:
Status ListInsert_L(LinkList L,int I,ElemType &e){
p=L->next;j=1;
while(p &&j<i-1){
p=p->next;
j++;
}
s=(LinkList) malloc (sizeof(LNode));
s->data=e;
s->next=p->next;
p->next=s;
return OK;
}

0 条评论