您好，欢迎来到六九路网。
科技 教育 生活 旅游 时尚 美容 美食 健康 体育 游戏 汽车 家电
搜索
您的当前位置：首页双向链表和静态链表

双向链表和静态链表

来源：六九路网

一，双向链表

双向链表每个node都有两个指针，分别指向前驱和后继。从头结点后第一个结点开始，都可以访问它的前驱结点和后继结点。

1.老师的代码

        1.1结构体


typedef struct DoubleLinkedNode{
    char data;
    struct DoubleLinkedNode *previous;
    struct DoubleLinkedNode *next;
}DLNode,*DLNodePtr;

        1.2初始化


DLNodePtr initLinkList(){
    DLNodePtr tempHeader=(DLNodePtr)malloc(sizeof(struct DoubleLinkedNode));
    tempHeader->data='\0';
    tempHeader->previous=NULL;
    tempHeader->next=NULL;
    return tempHeader;
}

        1.3打印链表


void printList(DLNodePtr paraHeader){
    DLNodePtr p=paraHeader->next;
    while(p!=NULL){
        printf("%c",p->data);
        p=p->next;
    }
    printf("\r\n");
}

        1.4插入元素


void insertElement(DLNodePtr paraHeader,char paraChar,int paraPosition){
    DLNodePtr p,q,r;
    
    p=paraHeader;
    for(int i=0;i<paraPosition;i++){
        p=p->next;
        if(p==NULL){
            printf("The position %d is beyond the scope of the list.\r\n",paraPosition);
            return;
        }
    }
    
    q=(DLNodePtr)malloc(sizeof(struct DoubleLinkedNode));
    q->data=paraChar;
    
    r=p->next;
    q->next=p->next;
    q->previous=p;
    p->next=q;
    if(r!=NULL){
        r->previous=q;
    }
}

 例：在第一个元素后加入结点，data为'Char 3'

第一步：P指向Header,Q指向待加入结点

 第二步：通过循环使P找到指定位置，R指向指定位置后一个结点

 第三步：Q的next指向P的next，Q的previous指向P，Q的next指向R,R的previous指向Q

        1.5删除元素


void deleteElement(DLNodePtr paraHeader,char paraChar){
    DLNodePtr p,q,r;
    p=paraHeader;

    while((p->next!=NULL)&&(p->next->data!=paraChar)){
        p=p->next;
    }
    
    if(p->next==NULL){
        printf("The char '%c' does not exist.\r\n",paraChar);
        return;
    }

    q=p->next;
    r=q->next;
    p->next=r;
    if(r!=NULL){
        r->previous=p;
    }

    free(q);
}

 例：删除指定data为'Char 3'的结点

第一步：P指向Header

 第二步：通过循环使P指向指定位置，Q指向P结点后一个结点，R指向Q结点后一个结点

 第三步：P的next指向R，R的previous指向P，释放Q指向的内存

        1.6地址打印


void basicAddressTest(){
    DLNode tempNode1,tempNode2;
    
    tempNode1.data=4;
    tempNode1.next=NULL;

    tempNode2.data=6;
    tempNode2.next=NULL; 

    printf("The first node :%d,%d,%d\r\n",&tempNode1,&tempNode1.data,&tempNode1.next);
    printf("The second node :%d,%d,%d\r\n",&tempNode2,&tempNode2.data,&tempNode2.next);

    tempNode1.next=&tempNode2;
}

        1.7test函数


void insertDeleteTest(){
    
	DLNodePtr tempList=initLinkList();
    printList(tempList);

    insertElement(tempList,'H',0);
    insertElement(tempList,'e',1);
    insertElement(tempList,'l',2);
    insertElement(tempList,'l',3);
    insertElement(tempList,'o',4);
    insertElement(tempList,'!',5);
    printList(tempList);

    deleteElement(tempList,'e');
    deleteElement(tempList,'a');
    deleteElement(tempList,'o');
    //printf("YES\n");
    printList(tempList);

    insertElement(tempList,'o',1);
    printList(tempList);
}

        1.8运行结果

2.自己的代码

        2.1GET按位置查找，返回data


char get(Dnode pH,int pPos){
    
    //判断输入是否合法
	if(pPos<0){
		printf("ERROR! 请输入一个大于零的数!\n");
		return '\0';
	} 
	
	Dnode p=pH;
	int i;

    //通过循环使p指向相应位置
	for(i=0;i<pPos;++i){
		p=p->next;

        //若超过链表长度，输出原因并退出函数
		if(p==NULL){
			printf("ERROR! 超过限度！\n");
			return'\0';
		}	
	}
	
    //数据合法，返回data
	return p->data;
}

        2.2LOCATE按值查找，返回指针


Dnode locate(Dnode pH,char pC){
	Dnode p=pH;

    通过循环定位到结点
	while((p->next!=NULL)&&(p->next->data!=pC)){
		p=p->next;		
	}
	
	p=p->next;

    //p移动到链表末端则证明未找到
    //打印并退出
	if(p==NULL){
			printf("ERROR! 未找到！\n");
			return NULL;
	}
		
    //返回p
	return p;
}

        2.3清空链表


void destroy(Dnode pH){
	Dnode p=pH;
	Dnode q=pH->next;
	
    //通过循环依次清空
	while(q!=NULL){
		free(p);
		p=q;
		q=q->next;
		//printf("YES\n");
	}
	free(p);

    //打印提示信息
	printf("DESTROY END!\n");
}

        2.4我的test函数


void Test(){

    //创建链表
	Dnode t=init();
	printf("初始化 ：");
	printL(t);
	
    //加入元素测试
	printf("尾部添加元素 ：");
	inserttail(t,'c',0);
	inserttail(t,'s',1) ;
	inserttail(t,'d',2);
	inserttail(t,'n',3);
	printL(t);

    //删除元素测试
	printf("删除元素 ：");
	deleteL(t,'s');
	deleteL(t,'a');
	deleteL(t,'d');
	printL(t);
	
    //再次加入元素
	printf("在指定元素后加入 ：");
	inserttail(t,'w',1);
	inserttail(t,'o',2);
	inserttail(t,'p',8);
	printL(t);
	
    //GET测试
	char bb=get(t,2);
	printf("GET : %c\n",bb);
	char cc=get(t,7);
	printf("GET : %c\n",cc);
	
    //LOCATE测试
	Dnode tt=locate(t,'b');
	printf("LOCATE : %ld\n",tt);
	Dnode mm=locate(t,'o');
	printf("LOCATE : %ld\n",mm);
	
    //DESTROY测试
	destroy(t);
	
    //打印地址
	printAddress();
	
}

        2.5完整代码

#include <stdio.h>
#include <malloc.h>

typedef struct DoubleLinknode{
	char data;
	struct DoubleLinknode *previous;
	struct DoubleLinknode *next;
}DLnode,*Dnode;

Dnode init(){
	Dnode tHeared=(Dnode)malloc(sizeof(DLnode));
	tHeared->data='\0';
	tHeared->next=NULL;
	tHeared->previous=NULL;
	return tHeared;
}

void printL(Dnode pH){
	Dnode pr=pH->next;
	
	while(pr!=NULL){
		printf("%c",pr->data);
		pr=pr->next;
	}
	printf("\r\n");
}
	
void deleteL(Dnode pH,char pC){
	Dnode p,q,r;
	
	p=pH;
	while((p->next!=NULL)&&(p->next->data!=pC))
		p=p->next;
	
	if(p->next==NULL){
		printf("ERROR! 未找到\n");
		return; 
	}
	
	q=p->next;
	r=q->next;
	p->next=r;
	
	if(r!=NULL){
		r->previous=p;
	}
	free(q);	
}

void inserttail(Dnode pH,char pC,int pPos){
	Dnode p,q,r;
	
	if(pPos<0){
		printf("ERROR!请输入一个大于等于零的数！\n");
	}
	p=(Dnode)malloc(sizeof(DLnode));
	p->data=pC;
	p->next=NULL;
	p->previous=NULL;
	
	int i; q=pH;
	for(i=0;i<pPos;++i){
		q=q->next;
		if(q==NULL){
			printf("ERROR! 超过最大限度!\n");
			return;
		}
	}
	
	r=q->next;
	p->next=q->next;
	p->previous=q;
	q->next=p;
	
	if(r!=NULL){
		r->previous=p;
	}
	
}

char get(Dnode pH,int pPos){
	if(pPos<0){
		printf("ERROR! 请输入一个大于零的数!\n");
		return '\0';
	} //attention
	
	Dnode p=pH;
	int i;
	for(i=0;i<pPos;++i){
		p=p->next;
		if(p==NULL){
			printf("ERROR! 超过限度！\n");
			return'\0';
		}	
	}
	
	return p->data;
}


Dnode locate(Dnode pH,char pC){
	Dnode p=pH;

	while((p->next!=NULL)&&(p->next->data!=pC)){
		p=p->next;		
	}
	
	p=p->next;
	if(p==NULL){
			printf("ERROR! 未找到！\n");
			return NULL;
	}
		
	return p;
} 

void destroy(Dnode pH){
	Dnode p=pH;
	Dnode q=pH->next;
	
	while(q!=NULL){
		free(p);
		p=q;
		q=q->next;
		//printf("YES\n");
	}
	free(p);
	printf("DESTROY END!\n");
}

void printAddress(){
	DLnode p,q;
	p.data='m';p.next=NULL;p.previous=NULL;
	q.data='x';q.next=NULL;q.previous=NULL;
	
	printf("FRIST :%d,%d,%d,%d\n",&p,&p.data,&p.next,&p.previous);
	printf("SECOND :%d,%d,%d,%d\n",&q,&q.data,&q.next,&q.previous);
	
	p.next=&q;
	
}

void Test(){
	Dnode t=init();
	printf("初始化 ：");
	printL(t);
	
	printf("尾部添加元素 ：");
	inserttail(t,'c',0);
	inserttail(t,'s',1) ;
	inserttail(t,'d',2);
	inserttail(t,'n',3);
	printL(t);

	printf("删除元素 ：");
	deleteL(t,'s');
	deleteL(t,'a');
	deleteL(t,'d');
	printL(t);
	
	printf("在指定元素后加入 ：");
	inserttail(t,'w',1);
	inserttail(t,'o',2);
	inserttail(t,'p',8);
	printL(t);
	
	char bb=get(t,2);
	printf("GET : %c\n",bb);
	char cc=get(t,7);
	printf("GET : %c\n",cc);
	
	Dnode tt=locate(t,'b');
	printf("LOCATE : %ld\n",tt);
	Dnode mm=locate(t,'o');
	printf("LOCATE : %ld\n",mm);
	
	destroy(t);
	
	printAddress();
	
}

void main(){
	Test();
}

        2.6运行结果

 双向链表弥补了单链表只能从头结点开始访问链表中数据元素的缺陷。可以更为方便地访问链表元素。

二，静态链表

预先分配一定的储存空间，用于链表的后续使用。有标识符数组used，反映各结点使用情况。

1.1老师的代码

        1.1结构体


typedef struct StaticLinkedNode{
    char data;
    int next;
}*NodePtr;

typedef struct StaticLinkedList{
    NodePtr nodes;
    int* used;
}*ListPtr;

        1.2初始化


ListPtr initLinkedList(){
    ListPtr tempPtr=(ListPtr)malloc(sizeof(struct StaticLinkedList));

    tempPtr->nodes=(NodePtr)malloc(sizeof(struct StaticLinkedNode)*DEFAULT_SIZE);
    tempPtr->used=(int*)malloc(sizeof(int)*DEFAULT_SIZE);

    tempPtr->nodes[0].data='\0';
    tempPtr->nodes[0].next=-1;

    tempPtr->used[0]=1;
    for(int i=1;i<DEFAULT_SIZE;i++){
        tempPtr->used[i]=0;
    }
    
    return tempPtr;
}

        1.3打印元素


void printList(ListPtr paraListPtr){
    int p=0;
    while(p!=-1){
        printf("%c",paraListPtr->nodes[p].data);
        p=paraListPtr->nodes[p].next;
    }
    printf("\r\n");
}

        1.4加入元素


void insertElement(ListPtr paraListPtr,char paraChar,int paraPosition){
    int p,q,i;

    p=0;
    for(i=0;i<paraPosition;i++){
        p=paraListPtr->nodes[p].next;
        if(p==-1){
            printf("The position %d is beyond the scope of the list.\r\n",paraPosition);
            return;
        }
    }
 
    for(i=1;i<DEFAULT_SIZE;i++){
        if(paraListPtr->used[i]==0){
            printf("Space at %d allocated.\r\n",i);
            paraListPtr->used[i]=1;
            q=i;
            break;
        }
    }
    if(i==DEFAULT_SIZE){
        printf("No space,\r\n");
        return;
    }

    paraListPtr->nodes[q].data=paraChar;
    
    printf("Linking\r\n");
    paraListPtr->nodes[q].next=paraListPtr->nodes[p].next;
    paraListPtr->nodes[p].next=q;
}

 例：在第一个元素后加入data'C'

第一步：P通过循环找到指定位置(虚线为初始"指向"，实线为末状态)

     

 第二步：Q通过循环，在used数组中找到空闲空间

 第三步：将待加入数据加入序号Q(图中为1号)的data区域，并将序号P的next改为Q，used数组中序号Q的值改为1，表示已占用

          1.5删除元素


void deleteElement(ListPtr paraListPtr,char paraChar){
    int p,q;
    p=0;
    while((paraListPtr->nodes[p].next!=-1)&&(paraListPtr->nodes[paraListPtr->nodes[p].next].data!=paraChar)){
        p=paraListPtr->nodes[p].next;
    }

    if(paraListPtr->nodes[p].next==-1){
        printf("Cannot delete %c\r\n",paraChar);
        return;
    }

    q=paraListPtr->nodes[p].next;
    paraListPtr->nodes[p].next=paraListPtr->nodes[paraListPtr->nodes[p].next].next;

    paraListPtr->used[q]=0;
}

 例：删除data'C'所在结点

第一步：P通过循环找到指定位置(虚线为初始"指向"，实线为末状态)

   

 第二步：Q"指向"P的next，P的next值改为Q的next值

 第三步：将used数组中序号Q的值改为0，表示已释放，再次添加数据至此位置时，覆盖之前的数据即可

        1.6测试函数


void appendInsertDeleteTest(){
    ListPtr tempList=initLinkedList();
    printList(tempList);

    insertElement(tempList,'H',0);
    insertElement(tempList,'e',1);
    insertElement(tempList,'l',2);
    insertElement(tempList,'l',3);
    insertElement(tempList,'o',4);
    printList(tempList);

    printf("Delete 'e'.\r\n");
    deleteElement(tempList,'e');
    printf("Delete 'a'.\r\n");
    deleteElement(tempList,'a');
    printf("Delete 'o'.\r\n");
    deleteElement(tempList,'o');
    printList(tempList);

    insertElement(tempList,'x',1);
    printList(tempList);
}

        1.7运行结果

2.我的代码

        2.1按位置查找返回data


char get(Slist pH,int pPos){
    //pPos是否合法
	if(pPos<0){
		printf("ERROR! 请输入一个大于零的数!\n");
		return '\0';
	} 
	
	int p=0;
	int i;
    
    //通过循环，使p指向相应位置
	for(i=0;i<pPos;++i){
		p=pH->nodes[p].next;

        //若超过链表长度，输出原因，退出程序
		if(p==-1){
			printf("ERROR! 超过限度！\n");
			return'\0';
		}	
	}
	
    //参数合法，返回相应data
	return pH->nodes[p].data;
}

        2.2按值查找返回序号


int locate(Slist pH,char pC){
	int p=0;//p可以理解为类似指针的一个标识符

    //通过循环，使p“指向”待查找值
	while((pH->nodes[p].next!=-1)&&(pH->nodes[pH->nodes[p].next].data!=pC)){
		p=pH->nodes[p].next;		
	}
	
	p=pH->nodes[p].next;

    //若未找到，输出原因并退出
	if(p==-1){
			printf("ERROR! 未找到！\n");
			return 0;
	}
		
    //返回结点序号
	return p;
}

        2.3test函数


void Test(){

    //初始化
	Slist t=init();
	printf("初始化 ：\n");
	printL(t);
	
    //向里添加元素
	printf("尾部添加元素 ：\n");
	inserttail(t,'c',0);
	inserttail(t,'s',1) ;
	inserttail(t,'d',2);
	inserttail(t,'n',3);
	printf("TEST %c%c%c%c\n",t->nodes[1].data,t->nodes[2].data,t->nodes[3].data,t->nodes[4].data);
	printL(t);

    //删除元素测试
	printf("删除元素 ：\n");
	deleteL(t,'s');
	deleteL(t,'a');
	deleteL(t,'d');
	printL(t);
	
    //再次加入元素
	printf("在指定元素后加入 ：\n");
	inserttail(t,'w',1);
	inserttail(t,'o',2);
	inserttail(t,'p',8);
	printL(t);
	
    //GET测试
	char bb=get(t,2);
	printf("GET : %c\n",bb);
	char cc=get(t,7);
	printf("GET : %c\n",cc);
	
    //LOCATE测试
	int tt=locate(t,'b');
	printf("LOCATE : %d\n",tt);
	int mm=locate(t,'o');
	printf("LOCATE : %d\n",mm);
	
	//printAddress();
	
}

        2.4完整代码

#include <stdio.h>
#include <malloc.h>

#define DEFAULT_SIZE 5

typedef struct staticLinknode{
	char data;
	int next;
}*Snode;

typedef struct staticLinklist{
	Snode nodes;
	int* used; 
}*Slist;

Slist init(){
	Slist tHeader=(Slist)malloc(sizeof(struct staticLinklist));
	tHeader->nodes=(Snode)malloc(sizeof(struct staticLinknode)*DEFAULT_SIZE);
	tHeader->used=(int*)malloc(sizeof(int)*DEFAULT_SIZE);
	
	tHeader->nodes[0].data='\0';
	tHeader->nodes[0].next=-1;
	
	tHeader->used[0]=1;
	
	for(int i=1;i<DEFAULT_SIZE;i++) {
		tHeader->used[i]=0; 
	}
	return tHeader;
}

void printL(Slist pH){
    int p=0;
    while(p!=-1){
        printf("%c",pH->nodes[p].data);
        p=pH->nodes[p].next;
    }
    printf("\r\n");
}
void printLL(Slist pH){
    int p=0;
    while(p!=-1){
    	printf("P BEFORE %d\n",p);
        printf("%c",pH->nodes[p].data);
        p=pH->nodes[p].next;
        printf("P AFTER %d\n",p);
    }
    printf("\r\n");
}
	
void deleteL(Slist pH,char pC){
	int p,q;
	
	p=0;
	while((pH->nodes[p].next!=-1)&&(pH->nodes[pH->nodes[p].next].data!=pC)){
        p=pH->nodes[p].next;
    }

    if(pH->nodes[p].next==-1){
        printf("ERROR!该元素 %c 不存在！ \r\n",pC);
        return;
    }
	
	q=pH->nodes[p].next;
	pH->nodes[p].next=pH->nodes[q].next;
	
	pH->used[q]=0;
}

void inserttail(Slist pH,char pC,int pPos){
	int p,q;
	
	if(pPos<0){
		printf("ERROR!请输入一个大于等于零的数！\n");
	}
	p=0;
	
	int i;
	for(i=0;i<pPos;++i){
		p=pH->nodes[p].next;
		if(p==-1){
			printf("ERROR!超过最大限度！\n");
			return;
		}
	}
	
	for(i=1;i<DEFAULT_SIZE;++i){
		if(pH->used[i]==0){
			printf("占用 %d 结点！\n",i);
			pH->used[i]=1;
			q=i;
			break;
		}
	}
	if(i==DEFAULT_SIZE){
		printf("ERROR!空间已满！\n");
		return;
	}
	pH->nodes[q].data=pC;
	pH->nodes[q].next=pH->nodes[p].next;
	pH->nodes[p].next=q;
}

char get(Slist pH,int pPos){
	if(pPos<0){
		printf("ERROR! 请输入一个大于零的数!\n");
		return '\0';
	} //attention
	
	int p=0;
	int i;
	for(i=0;i<pPos;++i){
		p=pH->nodes[p].next;
		if(p==-1){
			printf("ERROR! 超过限度！\n");
			return'\0';
		}	
	}
	
	return pH->nodes[p].data;
}


int locate(Slist pH,char pC){
	int p=0;

	while((pH->nodes[p].next!=-1)&&(pH->nodes[pH->nodes[p].next].data!=pC)){
		p=pH->nodes[p].next;		
	}
	
	p=pH->nodes[p].next;
	if(p==-1){
			printf("ERROR! 未找到！\n");
			return 0;
	}
		
	return p;
} 


void Test(){
	Slist t=init();
	printf("初始化 ：\n");
	printL(t);
	
	printf("尾部添加元素 ：\n");
	inserttail(t,'c',0);
	inserttail(t,'s',1) ;
	inserttail(t,'d',2);
	inserttail(t,'n',3);
	printf("TEST %c%c%c%c\n",t->nodes[1].data,t->nodes[2].data,t->nodes[3].data,t->nodes[4].data);
	printL(t);

	printf("删除元素 ：\n");
	deleteL(t,'s');
	deleteL(t,'a');
	deleteL(t,'d');
	printL(t);
	
	printf("在指定元素后加入 ：\n");
	inserttail(t,'w',1);
	inserttail(t,'o',2);
	inserttail(t,'p',8);
	printL(t);
	
	char bb=get(t,2);
	printf("GET : %c\n",bb);
	char cc=get(t,7);
	printf("GET : %c\n",cc);
	
	int tt=locate(t,'b');
	printf("LOCATE : %d\n",tt);
	int mm=locate(t,'o');
	printf("LOCATE : %d\n",mm);
	
	//printAddress();
	
}

void main(){
	Test();
}

        2.5运行结果

 特点：1.在进行插入和删除操作时不需要批量移动元素，只需要修改“指针”，有链式存储结构的特点。
             2.分配空间固定，灵活性不高，仅仅适用于事先指定空间的情况。
             3.used数组反映各结点的使用情况，查找较为方便。

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文

Copyright © 2019- 69lv.com 版权所有 湘ICP备2023021910号-1

违法及侵权请联系：TEL:199 1889 7713 E-MAIL:2724546146@qq.com

本站由北京市万商天勤律师事务所王兴未律师提供法律服务