线性表和链表的基本操作：初始化·定位查询·插入元素·删除·查找·双向链表

淩亂°似流年 2023-07-09 08:29 25阅读 0赞

1.线性表和链表的结点定义、表定义不同，因而操作不同  
比较：  
①线性表定义：

#define LIST_INIT_SIZE 80
    #define LISTINCREMENT 10 //define后面不加分号
    typedef  char ElemType;
    typedef struct{
    	ElemType *elem;
    	int length;
    	int listsize;
    }SqList;

②链表结点定义：

typedef struct Node{
    	ElemType data;
    	Stuct Node *next;
    }Node,*LinkList //LinkList为结构指针

链表定义：

typedef struct{
    	Link head,tail;   //头结点，尾结点 
    	int len;//链表长度
    	Link current;//当前访问节点 
    }LinkList;

2.线性表的基本操作  
①初始化（创建线性表）

Status InitList_Sq(Sqlist &L){
    	L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
    	if(!e) exit(OVERFLOW);
    	L.length=0;
    	L.listsize=LIST_INIT_SIZE;
    	return OK;
    }

②定位查询

int LocateElem_Sq(Sqlist &L,ElemType e,Status(*compare)(ElemType,ElemType)){               
      int i=1;
      p=L.elem; 
      if(i<=L.length&&!(*compare)(*p++))//compare返回值为0时失败
      ++i;
      if(i<=L.length) return i;
      else return 0; 
    }

③插入元素

Status ListInsert(Sqlist &L,ElemType e,int pos){
    	if(pos>L.length||pos<1) exit(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; 
    	}
    	q=&(L.elem[pos-1]); 
        for(p=&(L.elem[L.length-1]);p>=q;--p) //数组从零开始，减一也表示最后一个元素 
        *(P+1)=*p //p变为P+1，右结合
    	*q=e;
    	++L.length;
    	return OK; 
    }

④删除

Status ListDelete(SqList &L,int pos,ElemType e){
    	if(pos<1||pos>L.length) exit(ERROR);
    	P=&(L.elem[pos-1]);
    	e=*p;
    	q=L.elem+L.length-1;
    	for(++p;p<=q;++p)
    	*(p-1)=*p;
    	--L.length;
    	return OK;
    }

2.链表的基本操作  
①插入元素

Status ListInsert(LinkList L,int pos,ElemType e){
    	p=L; //P指向（化为）头指针
    	j=0;
    	while(p&&j<pos-1){p=p_>next;++j;}
    	if(!p||j>pos-1) return ERROR;
    	S=(LinkList)malloc(sizeof(LNode));
    	s_>next=p_>next;
    	s_>data=e;
    	p_>next=s;
    	return OK; 
    }

②元素查找（位序i）

Status GetElem_L(Linklist L,int pos,ElemType e){
    	p=_>L.next;  
    	j=1;
    	if(p&&j<pos){p=p_>next;++j;}
    	if(!p||j>pos) return ERROR;
    	e=p_>data;
    	return OK;
    }

③元素删除

Status ListDelete_L(LinkList L,int pos,ElemType e){
    	p=L;
    	j=0;
    	while(p&&j<pos-1) {p_>next;++j;}
    	if(!(p_>next)||j>pso-1) return ERROR;
    	q=p_>next;p_>next=q_>next;
    	e=q_>data;
    	free(q);
    	return OK; 
    }

④建造链表  
（ 建立头指针、一个结点；相当于在两个结点中插入一个新节点 ）

void CreatList_L(LinkList &L,int n){ 
    	L=(LinkList)malloc(sizeof(LNode));
    	L_>next=NULL; //建立头节点 
        for(i=n;i>0;--i){
        	p=(LinkList)malloc(sizeof(LNode));
        	scanf("&d",&p_>data);
        	p_>next=L_>next;L_>next=p； 
    	}
    }

⑤插入其后  
（插入元素e在当前指针后 ）

Status InsAfter(LinkList &L,ElemType e){
    	if(!L.current) return ERROE;
    	if(!MakeNode(s,e)) return ERROR;//已封装
    	s_>next=L.current_>next;
    	L.current_>next=s;
    	return OK; 
    }

⑥删除其后

Status DelAfter(LinkList &L,ElemType &e){//删除当前指针之后的结点 
    	if(!current) return ERROR;
    	q=L.current_>enxt;
    	L.current_>next=q_>next;
    	e=q_>data;
    	Free(q);
    }

7.其它  
双向链表：

typedef struct DuLNode{  
    	ElemType data;
    	struct DuLNode *prior; //指向前驱的指针域 
    	struct DuLNode *next; //指向后继的指针域 
    }DuLNode,*DuLinkList;