c语言_双向链表代码

布满荆棘的人生 2023-07-05 13:25 89阅读 0赞

# 一、bidirectionalListTable.h文件 #

typedef struct Node{
    	struct Node *prior;
    	int elem;
    	struct Node *next;
    }node;
    
    #define initTableSize 5
    node * initTable(int n);
    void displayTable(node *head);
    int selectElem(node *head, int elem);
    node * amendElem(node *head, int add, int newElem);
    node * insertTable(node *head, int add, int elem);
    node * deletTable(node *head, int add);

# 二、bidirectionalListTable.cpp文件 #

#include"stdafx.h"
    #include"bidirectionalListTable.h"
    #include"stdlib.h"
    #include"stdio.h"
    
    //创建双向链表，初始化链表大小为5个原始，不包含头结点，第一个结点为首元结点
    node * initTable(int n) {    //n为初始化节点的个数
    	node *head = (node*)malloc(sizeof(node));//创建首元结点
    	head->prior = NULL;
    	head->elem = 1;
    	head->next = NULL;
    	node *temp = head;
    	for (int i = 2; i <= n; i++){
    		node * newNode = (node*)malloc(sizeof(node));
    		newNode->prior = temp;
    		newNode->elem = i;
    		newNode->next = NULL;
    		temp->next = newNode;
    		temp = temp->next;
    	}
    	return head;
    }
    
    //查找某个元素函数
    int selectElem(node *head,int elem){
    	node *temp = head;
    	int i = 0;
    	do
    	{
    		i++;
    		if (temp->elem == elem){
    			return i;
    		}
    		temp = temp->next;
    	}while (temp);
    	printf("没有查找到数据\n");
    	return -1;
    }
    
    //创建显示链表函数
    void displayTable(node *head){
    	node *temp = head;
    	printf("%d ", temp->elem);
    	while (temp->next){
    		temp = temp->next;
    		printf("%d ", temp->elem);
    
    	}
    	printf("\n");
    }
    
    //改链表中的数据
    node * amendElem(node *head, int add, int newElem){
    	node *temp = head;
    	int numCounter=0;
    	while (temp){
    		numCounter++;
    		temp = temp->next;
    	}
    	if (add > numCounter){
    		printf("更改位置无效.....插入位置需要不大于链表长度%d\n", numCounter);
    		return  head;
    	}
    	temp = head;
    	if (add == 1){
    		temp->elem = newElem;
    	}
    	else{
    		    for (int i = 2; i <= add; i++)
    			{
    			   temp = temp->next;
    		    }
    			temp->elem = newElem;
    	    }
    	return  head;
    }
    
    //增加链表的结点
    node * insertTable(node *head, int add, int elem){
    	node *temp = head;
    	int numCounter = 0;
    	while (temp){
    		numCounter++;
    		temp = temp->next;
    	}
    	if (add > (numCounter+1)){
    		printf("插入位置无效，，，插入位置要不大于%d\n", numCounter + 1);
    		return  head;
    	}
    	temp = head;
    	if (add == 1)
    	{
    		node *newNode = (node*)malloc(sizeof(node));
    		newNode->elem = elem;
    		newNode->prior = NULL;
    		newNode->next = temp;
    		head = newNode;
    	}
    	else if (add == (numCounter + 1))
    	{
    		for (int i = 2; i <= numCounter; i++){
    			temp = temp->next;
    		}
    		node *newNode = (node*)malloc(sizeof(node));
    		newNode->elem = elem;
    		newNode->prior = temp;
    		newNode->next = NULL;
    		temp->next = newNode;
    
    	}
    	else
    	{
    		for (int i = 2; i <= add; i++){
    			temp = temp->next;
    		}
    		node *newNode = (node*)malloc(sizeof(node));
    		newNode->elem = elem;
    		newNode->prior =temp->prior;
    		newNode->next = temp;
    		temp->prior = newNode;
    		temp = newNode->prior;
    		temp->next = newNode;
    	}
    
    	return  head;
    }
    //删除链表结点
    node * deletTable(node *head, int add){
    	node *temp = head;
    	int numCounter = 0;
    	while (temp){
    		numCounter++;
    		temp = temp->next;
    	}
    	if ((add > numCounter) || (add <1)){
    		printf("删除位置无效，，，插入位置要不大于%d... 不小于1\n", numCounter + 1);
    		return  head;
    	}
    	temp = head;
    	if (add == 1)
    	{
    		temp = temp->next;
    		free(head);
    		temp->prior=NULL;
    		head = temp;
    	}
    	else if (add == numCounter)
    	{
    		for (int i = 2; i <= add; i++){
    			temp = temp->next;
    		}
    		temp->prior->next = NULL;
    		free(temp);
    	}
    	else 
    	{
    		for (int i = 2; i <= add; i++){
    			temp = temp->next;
    		}
    		node *temp1 = temp->prior;
    		node *temp2 = temp->next;
    		temp1->next = temp2;
    		temp2->prior = temp1;
    		free(temp);
    	}
    	return head;
    }

# 三、测试程序 #

#include"bidirectionalListTable.h"
    
    int _tmain(int argc, _TCHAR* argv[])
    {
    	node *head = initTable(7);
    	displayTable(head);
    	
    	int num = 0;
    	num = selectElem(head, 3);
    	printf("查找的数据所在位置为：%d\n", num);
    
    	node *temp = amendElem(head,1, 4);
    	displayTable(temp);
    	temp=insertTable(head,1, 3);
    	displayTable(temp);
    
    	temp = deletTable(temp, 0);
    	displayTable(temp);
    	return 0;
    }