精华内容
下载资源
问答
  • 满足特征的数据,每个元素类型为DataType Opration InitList(L): 初始化操作,建立一个空的线性表 ListEmpty(L): 若线性表为空,返回ture,否则false ClearList(L): 清空线性表 GetElem(L,i,*e):将L中第i个元素...
    /*
    ADT 线性表list
    Data
    	满足特征的数据,每个元素类型为DataType
    Opration
    	InitList(L):    初始化操作,建立一个空的线性表
    	ListEmpty(L):   若线性表为空,返回ture,否则false
    	ClearList(L):   清空线性表
    	GetElem(L,i,*e):将L中第i个元素返回给e
    	LoacateElem(L,e):在L中查找与e相等元素,返回位置,没有返回0
    	ListInsert(*L,i,e):在L的第i个元素位置插入e
    	ListDelete(*L,i,*e):在L的第i个元素位置删除,并用e返回
    	ListLength(L)   :返回线性表L的元素个数
    endADT
    */
    

    1.线性表的顺序储存结构实现

    顺序结构需要三个条件;指定一个存储空间Maxsize;其次要知道存储的位置data[];最后要知道长度length
    
    //顺序存储的结构实现
    #include <stdio.h>
    #include <Windows.h>
    #define MAXSISZ 20
    typedef int ElemType;
    typedef struct
    {
    	ElemType data[MAXSISZ];
    	int length;
    }SqList;
    

    2.线性表顺序存储的操作

    查找、插入、删除、取值、修改
    
    2.1 线性表顺序存储取值操作
    两步即可完成:
    1.判断位置是否合法
    2.见数组值赋值返回
    
    //顺序存储元素获取,从1开始
    #define ERROR 0
    #define OK 1
    #define True	1
    #define False	0
    typedef int Status; //定义返回位置
    Status GetElem(SqList L,int i,ElemType* e)
    {
    	if (i>L.length ||i<1 ||L.length==0)
    	{
    		return ERROR;
    	}
    	*e =L.data[i-1];
    	return OK;
    }
    
    2.2线性表顺序存储插入值操作
    完成步骤:
    1.判断插入条件
    2.从后往前移动一个位置
    3.在i的位置停止,赋值
    
    Status ListInsert(SqList *L,int i,ElemType e)
    {
    	if (L->length==MAXSISZ)
    		return ERROR;
    	if (i>L->length+1 || i<0)  //i超出范围
    		return ERROR;
    	if (i<=L->length)
    	{
    		for (int j=L->length;j>=i-1;j--)
    			L->data[j+1]=L->data[j];
    		L->length = L->length+1;
    		L->data[i-1]=e;
    		return OK;
    	}
    }
    
    2.3线性表顺序存储删除元素操作
    步骤:
    1.检查合法性,非法抛出异常(i>length;i<0;)
    2.从i开始前移一个位置
    3.表长减1
    
    Status ListDelete(SqList *L,int i, ElemType *e)
    {
    	if (i<0)
    		return ERROR;
    	if (i>L->length)
    		return ERROR;
    	if (i>0 && i<=L->length)
    	{
    		*e=L->data[i-1];
    		for (int j=i-1;j<=L->length;j++)
    		{
    			L->data[j]=L->data[j+1];
    		}
    		return OK;
    	}
    }
    
    3.线性表的链式存储结构
    3.1 链表的定义与结构
    定义:像铁链一样的结构的线性表,铁链的每个环称为结点
    结点(node):铁链的一环,可以分为两部分:一部分用来扩张长度;一部分用来连接下一环;因此:结点是由数据域和指针域构成;铁链的头可能系的绳子:头指针
    
    3.2 链表的分类
    结点的定义:数据元素由数据域和指针域构成
    
    typedef struct Node
    {
    	ElemType data;  //数据域
    	struct Node *next; //指针域
    }Node;
    typedef struct Node *LinkList;  //定义了一个头指针,指向node
    
    
    3.2.1.单链表
    a. 单链表的读取:
    步骤:
    1.从头开始,不断读取下一个,直至返回
    2.未读取到时返回空
    
    Status GetElemLinkList(LinkList L,int i,ElemType *e)
    {
    	LinkList p; //声明一个指针
    	p=L->next;  //p指向l的首个指针
    	int j = 1;  //计数
    	while (p && j<i)
    	{
    		p->next;
    		j++;
    	}
    	if(!p || j>i)
    		return ERROR;
    	*e =p->data;
    	return OK;
    }
    
    b. 单链表的插入:
    步骤:
    1.循环读取定位到位置i
    2.生成一个空结点,存放e
    3.指针指向e地址,e的指针指向下一结点
    
    Status LinkListInsert(LinkList l,int i, ElemType e)
    {
    	LinkList p,s;    //声明一个指针
    	p=l->next;     //p指向l的首结点
    	int j = 1;    //计数器
    	while (p && j<i)
    	{
    		p->next;
    		j++;
    	}
    	if (!p ||j>i)
    	{
    		return ERROR;
    	}
    	s = (LinkList)malloc(sizeof	(Node));  //生成一个新结点
    	s->data = e;   //结点赋值
    	s->next=p->next;  //新结点指向下一结点
    	p->next=s;        //指向新结点
    	return OK;
    }
    
    c. 单链表的删除:
    步骤:
    1.循环读取定位到位置i
    2.指针指向下下个
    3.释放结点,返回e
    
    Status LinkListDelete(LinkList l,int i ,ElemType *e)
    {
    	LinkList p,q;
    	p =l->next;
    	int j =1;
    	while(p->next && j<i-1)
    	{
    		p=p->next;
    		j++;
    	}
    	if (!(p->next)||j>i)
    		return ERROR;
    	q=p->next;  //用q指向i
    	p->next=q->next;//将i指向换为i-1指向
    	*e=q->data;
    	free(q);
    	return OK;
    }
    
    d. 单链表的创建(头插法)
    定义:所谓头插法,就是指每个新结点都放在第一位
    步骤:
    1.产生一个空链表L
    2.声明指针p和计数器l
    3.l的头结点指向null
    4.循环插入新结点
    
    void CreateListHead(LinkList* l,int n)
    {
    	LinkList p;
    	int i;
    	srand(time(0));   //随机数种子
    	*l = (LinkList)malloc(sizeof(Node)); //产生一个头结点为空的链表l,为变量分配内存
    	(*l)->next=NULL;      //初始化指向空
    	for (i=0;i<n;i++)    //新结点插入l
    	{
    		p=(LinkList)malloc(sizeof(Node));
    		p->data=rand()%100+1;
    		p->next = (*l)->next;    //单链表的标准插入方法,p的next指向下一个结点
    		(*l)->next = p;          //l指向p
    	}
    }
    
    
    e.单链表的创建(尾插法)
    
    void CreateListTail(LinkList* l,int n)
    {
    	LinkList p,r;
    	int i;
    	srand(time(0));
    	*l = (LinkList)malloc(sizeof(Node));
    	r = *l;   //r为指向尾部的结点,尾插法,最重要的是知道尾结点的地址
    	for (i=0;i<n;i++)
    	{
    		p = (LinkList)malloc(sizeof(Node));
    		p->data = rand()%100+1;
    		r->next=p;   //尾结点的指针指向p
    		r=p;
    	}
    	r->next = NULL;   //尾结点指向空
    }
    
    f.单链表的清空
    
    Status ClearSList(LinkList *l)
    {
    	LinkList p,q;
    	p = (*l)->next;
    	while (p)
    	{
    		q=p->next;
    		free(p);
    		p=q;
    	}
    	(*l)->next=NULL;  //头结点指向空
    	return OK;
    }
    
    双链表
    循环链表
    静态链表
    
    f:测试入口
    
    void main()
    {
    	/*
    	//线性表顺序存储的测试用例
    	SqList  l;
    	l.length = 10;
    	ElemType e;
    	for (int i=0;i<l.length;i++)
    	{
    		l.data[i]=i;
    	}
    	GetElem(l,3,&e);
    	ListInsert(&l,3,5);      //在第三个位置插入5
    	ListDelete(&l,3,&e);
    	printf("%d\n",l.data[2]);   //&e表示引用e的地址,e为一个变量;*e表示e指向的内容,e为一个指针变量
    	system("pause");
    	*/
    	/*
    	单链表的单元测试
    	*/
    	ElemType e;
    	LinkList  m;   //声明一个结点
    	m = NULL;       //结点初始化为空
    	CreateListHead(&m,10);   //头插法创建单链表
    	//printList(&m);
    	CreateListTail(&m,10);    //尾插法创建链表
    	printList(&m);
    	LinkListDelete(m,2,&e);   //单链表删除第i个元素,返回给e
    	printList(&m);
    	LinkListInsert(m,2,99);   //单链表的插入,第2个位置插入99
    	printList(&m);
    	GetElemLinkList(m,2,&e);   //单链表的查询,获取第2个元素的值,返回给e
    	printf("%d\n",e);
    	ClearSList(&m);           //清空单链表
    	printList(&m);
    	system("pause");	
    }
    
    展开全文
  • 使用C语言实现数据结构 表,原子,链表,栈,集合,动态数组,环,序列,位向量,线程,异常,精度计算,内存管理,字符串 包含了不透明指针,断言处理时机,二级指针的用法,宏定义,复杂结构体,setjmp/longjmp,...
  • c语言实现基本数据结构(链表) 感觉写链表比较考验对指针的理解。。。 下图可以方便对链表中指针进行理解 List* L; //新建链表指针,没有指向任何东西 L = (List *)malloc(sizeof(List)) //从堆中分配List...

    用c语言实现基本数据结构(链表)

    感觉写链表比较考验对指针的理解。。。
    下图可以方便对链表中指针进行理解

    List* L; //新建链表指针,没有指向任何东西
    L = (List *malloc(sizeof(List)) //从堆中分配List大小的内存空间,赋给L,L就有了指向的空间。
    *L //L指向的结构体,一般不用这种写法(主要是不方便)
    L->data //L指向的结构体中的数据
    L->next //L指向的结构体中的指针next,一个指针类型数据
    //c语言的链表中,一个节点的意思就是一个结构体。
    

    首先是单链表
    结构体如下

    typedef struct Linklist{
    	int data;
    	struct Linklist* next;
    }List;
    

    方法如下

    void InitList(List *L); //初始化链表(建立头节点)
    void CreateList(List *L);//创建链表,先输入待输入数据个数,再输入数据
    List* FindNode(List *L, int n);//找到第n个节点(从1开始)
    void InsertNode(List* L, int n, int data);//在第n个节点后插入节点
    int ListLength(List* L);//返回链表长度
    int DelNode(List *L, int n);//删除第n个节点
    void PrintfList(List *L);//输出所有节点数据
    

    完整代码如下

    #include <stdio.h>
    #include <stdlib.h>
    
    typedef struct Linklist{
    	int data;
    	struct Linklist* next;
    }List;
    
    void InitList(List *L){
    	L = (List *)malloc(sizeof(List));
    	L->data = 0;
    	L->next = NULL;
    	if(L == NULL){
    		printf("create list wrong!!!\n");
    	}
    }
    
    void CreateList(List *L){
    	List *tailpoint = L;
    	int len = 0;	
    	while(len <= 0){
    		printf("over input data length!\n");
    		scanf("%d", &len);
    	}
    	for(int i = 0; i < len; i++){
    		List* node = (List *)malloc(sizeof(List));
    		scanf("%d", &node->data);
    		node->next = NULL;
    		tailpoint->next = node;
    		tailpoint = node;
    	}
    	printf("end input!\n");
    }
    
    List* FindNode(List *L, int n){
    	List *p = L;
    	for(int i = 0; i < n; i++){
    		if(p == NULL){
    			printf("list crossover!!!\n");
    			return NULL;
    		}
    		p = p->next;
    	}
    	return p;
    }
    
    void InsertNode(List* L, int n, int data){
    	List* p = FindNode(L, n);
    	List* node = (List*)malloc(sizeof(List));
    	node->data = data;
    	node->next = p->next;
    	p->next = node;
    }
    
    int ListLength(List* L){
    	List *p = L;
    	int len = 0;
    	while(p->next != NULL){
    		p = p->next;
    		len++;
    	}
    	return len;
    }
    
    
    int DelNode(List *L, int n){
    	List *pre = FindNode(L, n-1);
    	if(pre->next == NULL){
    		printf("list crossover\n");
    		return 0;
    	}
    	List *p = pre->next;
    	pre->next = p->next;
    	free(p);
    	return 1;
    }
    
    void PrintfList(List *L){
    	List *p = L->next;
    	while(p != NULL){
    		printf("%d ", p->data);
    		p = p->next;
    	}
    	printf("\n");
    }
    

    测试代码如下

    #include"myList.h"
    	
    int main(){
    	List *list;
    	List *node;
    	printf("-----------------a\n");
    	InitList(list);
    	printf("-----------------b\n");
    	CreateList(list);
    	PrintfList(list);
    	printf("-----------------c\n");
    	node = FindNode(list, 1);
    	printf("%d\n", node->data);
    	printf("-----------------d\n");
    	InsertNode(list, 3, 89);
    	PrintfList(list);
    	printf("-----------------e\n");
    	printf("%d\n", ListLength(list));
    	printf("-----------------f\n");
    	DelNode(list, 2);
    	PrintfList(list);
    	return 0;
    }
    
    展开全文
  • 忽然想起来,大概在两年之前学习C语言的时候,曾经用C语言写过一些通用的数据结构。主要也就实现了链表、队列、椎、HashSet,还有HashMap。当时只是知道标准的C语言没有这方面的类库,后来才知道有很多第三方的...

       忽然想起来,大概在两年之前学习C语言的时候,曾经用C语言写过一些通用的数据结构。主要也就实现了链表、队列、椎、HashSet,还有HashMap。当时只是知道标准的C语言中没有这方面的类库,后来才知道有很多第三方的类似这样的类库。废话不多说,先把代码粘过来。

    下面实现的是通用链表,注意链表中只存储了指针,没有储存实际的数据。

    头文件

    1. /*************** 
    2.  File myList.h 
    3. *******************/  
    4.   
    5. #ifndef MYLIST_H_INCLUDED  
    6. #define MYLIST_H_INCLUDED  
    7. #include <stdio.h>  
    8.   
    9.   
    10. typedef struct myNode  
    11. {  
    12.     void  data;  
    13.     struct myNode *next;  
    14. } MyNode;  
    15.   
    16. typedef struct myList  
    17. {  
    18.     MyNode  first;  
    19.     MyNode  last;  
    20.     int count;  
    21.     int (*equal)(void  a, void  b);  
    22. } MyList;  
    23.   
    24. typedef struct myListIterator  
    25. {  
    26.     MyNode  p;  
    27.     int count;  
    28.     int allSize;  
    29. } MyListIterator;  
    30.   
    31. //创建链表  
    32. MyList  createMyList();  
    33.   
    34. //创建链表,带有相等参数,用于查找  
    35. MyList  createMySearchList(int(equal)(void  a, void  b));  
    36.   
    37. //释放链表  
    38. void freeMyList(MyList  list);  
    39.   
    40. //插入在尾部  
    41. void myListInsertDataAtLast(MyList* const list, void const data);  
    42.   
    43. //插入在首部  
    44. void myListInsertDataAtFirst(MyList  const list, void const data);  
    45.   
    46. //插入  
    47. void myListInsertDataAt(MyList  const list, void const data, int index);  
    48.   
    49. //删除在尾部  
    50. void myListRemoveDataAtLast(MyList* const list);  
    51.   
    52. //删除在首部  
    53. void myListRemoveDataAtFirst(MyList  const list);  
    54.   
    55. //删除  
    56. void myListRemoveDataAt(MyList const list, int index);  
    57.   
    58. //删除对象,返回是否删除成功  
    59. int myListRemoveDataObject(MyList* const list, void  data);  
    60.   
    61. //长度  
    62. int myListGetSize(const MyList  const list);  
    63.   
    64. //打印  
    65. void myListOutput(const MyList  const list, void(*pt)(const void  const));  
    66.   
    67. //取得数据  
    68. void myListGetDataAt(const MyList  const list, int index);  
    69.   
    70. //取得第一个数据  
    71. void myListGetDataAtFirst(const MyList  const list);  
    72.   
    73. //取得最后一个数据  
    74. void myListGetDataAtLast(const MyList  const list);  
    75.   
    76. //查找某个数据的位置,如果equal方法为空,比较地址,否则调用equal方法  
    77. //如果不存在返回-1,如果存在,返回出现的第一个位置  
    78. int myListFindDataIndex(const MyList  const list, void  data);  
    79.   
    80. //创建遍历器  
    81. MyListIterator* createMyListIterator(const MyList  const list);  
    82.   
    83. //释放遍历器  
    84. void freeMyListIterator(MyListIterator iterator);  
    85.   
    86. //遍历器是否有下一个元素  
    87. int myListIteratorHasNext(const MyListIterator* const iterator);  
    88.   
    89. //返回遍历器的下一个元素  
    90. void  myListIteratorNext(MyListIterator const iterator);  
    91.   
    92. #endif // MYLIST_H_INCLUDED  

    源文件

    1. /*************** 
    2.  File myList.c 
    3. *******************/  
    4.   
    5. #include “myList.h”  
    6. #include <stdlib.h>  
    7. //创建链表  
    8. MyList  createMyList()  
    9. {  
    10.     MyList  re = (MyList ) malloc(sizeof(MyList));  
    11.     re->count = 0;  
    12.     re->first = NULL;  
    13.     re->last = NULL;  
    14.     re->equal = NULL;  
    15.     return re;  
    16. }  
    17.   
    18. //释放链表  
    19. void freeMyList(MyList  list)  
    20. {  
    21.     MyNode  p;  
    22.     while (list->first)  
    23.     {  
    24.         p = list->first->next;  
    25.         free(list->first);  
    26.         list->first = p;  
    27.     }  
    28.     free(list);  
    29. }  
    30.   
    31. //插入在尾部  
    32. void myListInsertDataAtLast(MyList  const list, void const data)  
    33. {  
    34.     MyNode  node = (MyNode ) malloc(sizeof(MyNode));  
    35.     node->data = data;  
    36.     node->next = NULL;  
    37.     if (list->count)  
    38.     {  
    39.         list->last->next = node;  
    40.         list->last = node;  
    41.     }  
    42.     else  
    43.     {  
    44.         list->first = node;  
    45.         list->last = node;  
    46.     }  
    47.     (list->count)++;  
    48. }  
    49.   
    50. //插入在首部  
    51. void myListInsertDataAtFirst(MyList  const list, void const data)  
    52. {  
    53.     MyNode  node = (MyNode ) malloc(sizeof(MyNode));  
    54.     node->data = data;  
    55.     node->next = NULL;  
    56.   
    57.     if (list->count)  
    58.     {  
    59.         node->next = list->first;  
    60.         list->first = node;  
    61.     }  
    62.     else  
    63.     {  
    64.         list->first = node;  
    65.         list->last = node;  
    66.     }  
    67.     (list->count)++;  
    68. }  
    69.   
    70. //长度  
    71. int myListGetSize(const MyList  const list)  
    72. {  
    73.     return list->count;  
    74. }  
    75.   
    76. //打印  
    77. void myListOutput(const MyList  const list, void(*pt)(const void  const))  
    78. {  
    79.     MyNode  p = list->first;  
    80.     while (p)  
    81.     {  
    82.         (*pt)(p->data);  
    83.         p = p->next;  
    84.     }  
    85. }  
    86.   
    87. //删除在尾部  
    88. void myListRemoveDataAtLast(MyList* const list)  
    89. {  
    90.     if (list->count == 1)  
    91.     {  
    92.         return myListRemoveDataAtFirst(list);  
    93.     }  
    94.     MyNode  p = list->first;  
    95.     while (p->next != list->last)  
    96.     {  
    97.         p = p->next;  
    98.     }  
    99.     void *re = list->last->data;  
    100.     free(list->last);  
    101.     p->next = NULL;  
    102.     list->last = p;  
    103.     (list->count)–;  
    104.     return re;  
    105. }  
    106.   
    107. //删除在首部  
    108. void myListRemoveDataAtFirst(MyList  const list)  
    109. {  
    110.     MyNode *p = list->first;  
    111.     list->first = p->next;  
    112.     void  re = p->data;  
    113.     free(p);  
    114.     (list->count)–;  
    115.     if (list->count == 0)  
    116.     {  
    117.         list->last = NULL;  
    118.     }  
    119.     return re;  
    120. }  
    121.   
    122. //插入  
    123. void myListInsertDataAt(MyList  const list, void const data, int index)  
    124. {  
    125.     if (index == 0)  
    126.     {  
    127.         myListInsertDataAtFirst(list, data);  
    128.         return;  
    129.     }  
    130.     if (index == list->count)  
    131.     {  
    132.         myListInsertDataAtLast(list, data);  
    133.         return;  
    134.     }  
    135.     MyNode  node = (MyNode ) malloc(sizeof(MyNode));  
    136.     node->data = data;  
    137.     node->next = NULL;  
    138.   
    139.     MyNode  p = list->first;  
    140.     for (int i = 0; i < index - 1; i++)  
    141.     {  
    142.         p = p->next;  
    143.     }  
    144.     node->next = p->next;  
    145.     p->next = node;  
    146.   
    147.     (list->count)++;  
    148. }  
    149.   
    150. //删除  
    151. void myListRemoveDataAt(MyList* const list, int index)  
    152. {  
    153.     if (index == 0)  
    154.     {  
    155.         return myListRemoveDataAtFirst(list);  
    156.     }  
    157.     if (index == list->count - 1)  
    158.     {  
    159.         return myListRemoveDataAtLast(list);  
    160.     }  
    161.   
    162.     MyNode  p = list->first;  
    163.     for (int i = 0; i < index - 1; i++)  
    164.     {  
    165.         p = p->next;  
    166.     }  
    167.     MyNode *tp = p->next;  
    168.     p->next = p->next->next;  
    169.     void  re = tp->data;  
    170.     free(tp);  
    171.     (list->count)–;  
    172.     return re;  
    173. }  
    174.   
    175. //取得数据  
    176. void myListGetDataAt(const MyList  const list, int index)  
    177. {  
    178.     if (index == list->count - 1)  
    179.     {  
    180.         return myListGetDataAtLast(list);  
    181.     }  
    182.     MyNode  p = list->first;  
    183.     for (int i = 0; i < index; i++)  
    184.     {  
    185.         p = p->next;  
    186.     }  
    187.     return p->data;  
    188. }  
    189.   
    190. //取得第一个数据  
    191. void myListGetDataAtFirst(const MyList  const list)  
    192. {  
    193.     return list->first->data;  
    194. }  
    195.   
    196. //取得最后一个数据  
    197. void myListGetDataAtLast(const MyList  const list)  
    198. {  
    199.     return list->last->data;  
    200. }  
    201.   
    202. //查找某个数据的位置,如果equal方法为空,比较地址,否则调用equal方法  
    203. //如果不存在返回-1,如果存在,返回出现的第一个位置  
    204. int myListFindDataIndex(const MyList  const list, void  data)  
    205. {  
    206.     MyNode  p = list->first;  
    207.     int re = 0;  
    208.     if (list->equal)  
    209.     {  
    210.         while (p)  
    211.         {  
    212.             if (p->data == data || ((list->equal))(p->data, data))  
    213.             {  
    214.                 return re;  
    215.             }  
    216.             re++;  
    217.             p = p->next;  
    218.         }  
    219.   
    220.     }  
    221.     else  
    222.     {  
    223.         while (p)  
    224.         {  
    225.             if (p->data == data)  
    226.             {  
    227.                 return re;  
    228.             }  
    229.             re++;  
    230.             p = p->next;  
    231.         }  
    232.     }  
    233.     return -1;  
    234. }  
    235.   
    236. //创建链表,带有相等参数,用于查找  
    237. MyList  createMySearchList(int(equal)(void  a, void  b))  
    238. {  
    239.     MyList  re = createMyList();  
    240.     re->equal = equal;  
    241.     return re;  
    242. }  
    243.   
    244. //创建遍历器  
    245. MyListIterator* createMyListIterator(const MyList  const list)  
    246. {  
    247.     MyListIterator  re = (MyListIterator ) malloc(sizeof(MyListIterator));  
    248.     re->p = list->first;  
    249.     re->allSize = list->count;  
    250.     re->count = 0;  
    251.     return re;  
    252. }  
    253.   
    254. //释放遍历器  
    255. void freeMyListIterator(MyListIterator iterator)  
    256. {  
    257.     free(iterator);  
    258. }  
    259.   
    260. //遍历器是否有下一个元素  
    261. int myListIteratorHasNext(const MyListIterator* const iterator)  
    262. {  
    263.     return iterator->count < iterator->allSize;  
    264. }  
    265.   
    266. //返回遍历器的下一个元素  
    267. void  myListIteratorNext(MyListIterator const iterator)  
    268. {  
    269.     void  re = iterator->p->data;  
    270.     iterator->p = iterator->p->next;  
    271.     (iterator->count)++;  
    272.     return re;  
    273. }  
    274.   
    275. //删除对象,返回是否删除成功  
    276. int myListRemoveDataObject(MyList const list, void  data)  
    277. {  
    278.     MyListIterator  it = createMyListIterator(list);  
    279.     int a = 0;  
    280.     while (myListIteratorHasNext(it))  
    281.     {  
    282.         void  ld = myListIteratorNext(it);  
    283.         if (data == ld || (list->equal != NULL && ((list->equal))(ld, data)))  
    284.         {  
    285.             a = 1;  
    286.             break;  
    287.         }  
    288.     }  
    289.     if (a)  
    290.     {  
    291.         myListRemoveDataAt(list, it->count - 1);  
    292.     }  
    293.     return a;  
    294. }  

    测试文件

    1. /*************** 
    2.  File main.c 
    3.  test for MyList 
    4. ****************/  
    5. #include <stdio.h>  
    6. #include <stdlib.h>  
    7. #include “myList.h”  
    8.   
    9. typedef struct a  
    10. {  
    11.     int i;  
    12.     char c;  
    13. } A;  
    14.   
    15. void ppt(const void const p)  
    16. {  
    17.     A  pp= p;  
    18.     printf(”%d(%c) ”, pp->i, pp->c);  
    19. }  
    20.   
    21.   
    22. int main()  
    23. {  
    24.     const int S =10;  
    25.   
    26.     //创建并初始化数据  
    27.     A  data= malloc(sizeof(A)*S);  
    28.     for (int i=0; i< S; i++)  
    29.     {  
    30.         data[i].i=i;  
    31.         data[i].c=(char)(‘A’+0);  
    32.     }  
    33.   
    34.     //创建链表  
    35.     MyList  list= createMyList();  
    36.   
    37.     //测试三种插入方法  
    38.     myListInsertDataAtLast( list, &data[0]);  
    39.     myListInsertDataAtFirst( list, &data[4]);  
    40.     myListInsertDataAt(list, &data[1], 1 );  
    41.   
    42.   
    43.     //测试查找  
    44.     int index = myListFindDataIndex(list, &data[2]);  
    45.     printf(”%d\n”, index);  
    46.     index = myListFindDataIndex(list, &data[4]);  
    47.     printf(”%d\n”, index);  
    48.   
    49.     //输出  
    50.     myListOutput(list, ppt );  
    51.     puts(”“);  
    52.   
    53.     //测试使用迭代器输出  
    54.     MyListIterator  it = createMyListIterator(list);  
    55.     while(myListIteratorHasNext(it))  
    56.     {  
    57.         A  pp = myListIteratorNext(it);  
    58.         printf(”%d[%c] ”, pp->i, pp->c);  
    59.     }  
    60.     puts(”“);  
    61.     //释放迭代器  
    62.     freeMyListIterator(it);  
    63.   
    64.     //释放链表  
    65.     freeMyList(list);  
    66.   
    67.     //释放数据  
    68.     free(data);  
    69.     return 0;  
    70. }  

    展开全文
  • 双链表 双链表相较于单链表多...2.如果单链表还不会的,请移步用c语言实现数据结构——单链表 这样回头双链表,会非常简单。 3.删除节点那里,需要处理一下如果删除最后节点。代码如下: /* Function name : deleteNode

    双链表

    双链表相较于单链表多了个前驱指针(perv),这样做的优点:每个节点的前驱和后继都可以轻松的找到,缺点就是会多一个指针空间。当然,遇到问题到底是用单链表还是双链表看具体情况。

    原理

    1.笔者认为,双链表和单链表其实没有太大的区别,就是多了一个前驱指针,较于单链表就是每个步骤中要加入前驱而已。
    2.如果单链表还不会的,请移步用c语言实现数据结构——单链表
    这样回头双链表,会非常简单。
    3.删除节点那里,需要处理一下如果删除最后节点。代码如下:

    /*
    Function name : deleteNode
    Description : 删除一个节点
    Parameter   :
                 @head : 双链表的头节点
    			 @i    : 要删除的位置
    return      :返回1成功,其他失败
    */
    int deleteNode(Node *head, int i)
    {
    	int length = getLength(head);/*获取链表长度*/
    	Node *temp = head;
    	if (i<1 || i>length ) return 0;/*位置不合法*/
    	for (int k = 0; k < i - 1; k++)/*遍历到要删除节点的前面*/
    	{
    		temp = temp->next;
    	}
    	if (i == length)/*如果删除最后一个节点*/
    	{
    		Node *p = temp->next;/*即将删除的节点*/
    		p->perv = NULL;/*删除节点的前驱要空,后继原本就是空*/
    		free(p); /*释放*/
    		temp->next = NULL;/*要删除节点的前驱要置空*/
    		return 1;
    	}
    	Node *p = temp->next;/*即将删除的节点*/
    	temp->next = temp->next->next;/*直接连接到下一个节点*/
    	temp->next->next->perv = temp;/*前驱指针也要指回去*/
    	free(p);/*释放*/
    	return 1;
    }
    

    大家可以想想,为什么这里要加判断是不是最后的节点。提示一下,问题出在temp->next->next->perv=temp;

    代码和运行截图

    看这个代码起码你要知道基本原理。要不然看起来会很累

    /**********************************************
    @File name : DoubleLinkList.c
    @Author    : StudyCcYa
    @Version   : 1.0
    @Data      : 2020-11-08
    @Description: 用c语言实现数据结构——双链表
    ***********************************************/
    #include <stdio.h>
    #include <stdlib.h>
    #include <assert.h>
    
    typedef int Type;
    
    /*双链表节点的结构体*/
    typedef struct Node
    {
    	Type data;
    	struct Node *next;/*后继指针*/
    	struct Node *perv;/*前驱指针*/
    }Node;
    
    
    /*函数声明*/
    Node *initNode(int elem);/*初始化双链表节点*/
    Node *emptyNode();/*空节点*/
    Node *creatListHead();/*头插法创建一个双链表*/
    Node *creatListTail();/*尾插法创建一个双链表*/
    int printfList(Node *head);/*输出双链表*/
    int getLength(Node *head);/*获取双链表长度*/
    int insertNode(Node *head,int i,Type elem);/*增加一个节点*/
    int deleteNode(Node *head,int i);/*删除一个节点*/
    Type getNode(Node *head,int i);/*查找节点*/
    int changeNode(Node *head, int i, Type elem);/*改变节点数据*/
    /*
    Function name : initNode
    Description   : 初始化双链表节点
    Parameter     :
                    无
    return        : 返回一个双链表节点成功,其他失败
    */
    Node *initNode(int elem)
    {
    	Node *temp = (Node *)malloc(sizeof(Node));/*申请一个节点空间*/
    	assert(temp);/*断言,如果申请失败报错*/
    	temp->data = elem;
    	temp->next = NULL;
    	temp->perv = NULL;
    	return temp;
    }
    
    /*
    Function name : emptyNode
    Description   : 空节点
    Parameter     :
                    无
    return        : 返回一个双链表空节点成功,其他失败
    */
    Node *emptyNode()
    {
    	Node *temp = (Node *)malloc(sizeof(Node));/*申请一个节点空间*/
    	assert(temp);/*断言,如果申请失败报错*/
    	temp->next = NULL;
    	temp->perv = NULL;
    	return temp;
    }
    
    /*
    Function name : creatListHead
    Description : 头插法创建一个双链表
    Parameter   :
                  无
    return      :返回一个双链表头成功,其他失败
    */
    Node *creatListHead()
    {
    	int n;/*要创建的链表节点个数*/
    	Type elem;/*节点数据*/
    	Node *head = emptyNode();
    	printf("请输入要创建双链表节点的个数(头插):\n");
    	scanf("%d",&n);
    	printf("请输入数据:\n");
    	for (int i = 0; i < n; i++)
    	{
    		scanf("%d",&elem);
    		Node *temp = initNode(elem);
    		temp->next = head->next;/*新节点的后继指针指向头指针的后继*/
    		temp->perv = head;/*新节点的前驱指向头节点*/
    		head->next = temp;/*头节点的后继指向前驱*/
    	}
    	return head;
    }
    
    /*
    Function name : creatListTail
    Description : 尾插法创建一个双链表
    Parameter   :
    无
    return      :返回一个双链表头成功,其他失败
    */
    Node *creatListTail()
    {
    	int n;/*要创建的链表节点个数*/
    	Type elem;/*节点数据*/
    	Node *head = emptyNode();
    	Node *tail = head;/*一开始头节点和尾节点指向一起*/
    	printf("请输入要创建双链表节点的个数(尾插):\n");
    	scanf("%d", &n);
    	printf("请输入数据:\n");
    	for (int i = 0; i < n; i++)
    	{
    		scanf("%d", &elem);
    		Node *temp = initNode(elem);
    		tail->next = temp;
    		temp->perv = tail;
    		tail = tail->next;
    	}
    	return head;
    }
    
    /*
    Function name : printfList
    Description : 输出双链表
    Parameter   :
                  @head : 双链表的头节点
    return      :返回1成功,其他失败
    */
    int printfList(Node *head)
    {
    	Node *temp = head;
    	for (temp = head->next; temp != NULL; temp = temp->next)
    	{
    		if (temp->next != NULL)
    		{
    			printf("%d<->",temp->data);
    		}
    		else
    		{
    			printf("%d\n",temp->data);
    			return 1;
    		}
    	}
    	return 0;
    }
    
    /*
    Function name : getLength
    Description : 获取双链表长度
    Parameter   :
                 @head : 双链表的头节点
    return      :返回链表长度成功,其他失败
    */
    int getLength(Node *head)
    {
    	int i=0;/*循环变量*/
    	Node *temp = head;/*防止头指针丢失*/
    	while (temp != NULL)/*循环遍历链表*/
    	{
    		i++;
    		temp = temp->next; 
    	}
    	return i - 1;/*头指针不存放数据不算*/
    }
    
    /*
    Function name : insertNode
    Description : 增加一个节点
    Parameter   :
                 @head : 双链表的头节点
    			 @i    : 要插入的位置
    			 @elem : 要插入的数据
    return      :返回1成功,其他失败
    */
    int insertNode(Node *head, int i ,Type elem)
    {
    	int length = getLength(head);/*获取链表长度*/
    	Node *temp = head;
    	if (i<1 || i>length + 1) return 0;/*位置不合法*/
    	for (int k = 0; k < i - 1; k++)/*遍历到要插入节点的前面*/
    	{
    		temp = temp->next;
    	}
    	Node *newNode = initNode(elem);
    	newNode->next = temp->next;/*头插*/
    	newNode->perv = temp;
    	temp->next = newNode;
    	return 1;
    }
    
    /*
    Function name : deleteNode
    Description : 删除一个节点
    Parameter   :
                 @head : 双链表的头节点
    			 @i    : 要删除的位置
    return      :返回1成功,其他失败
    */
    int deleteNode(Node *head, int i)
    {
    	int length = getLength(head);/*获取链表长度*/
    	Node *temp = head;
    	if (i<1 || i>length ) return 0;/*位置不合法*/
    	for (int k = 0; k < i - 1; k++)/*遍历到要删除节点的前面*/
    	{
    		temp = temp->next;
    	}
    	if (i == length)/*如果删除最后一个节点*/
    	{
    		Node *p = temp->next;/*即将删除的节点*/
    		p->perv = NULL;/*删除节点的前驱要空,后继原本就是空*/
    		free(p); /*释放*/
    		temp->next = NULL;/*要删除节点的前驱要置空*/
    		return 1;
    	}
    	Node *p = temp->next;/*即将删除的节点*/
    	temp->next = temp->next->next;/*直接连接到下一个节点*/
    	temp->next->next->perv = temp;/*前驱指针也要指回去*/
    	free(p);/*释放*/
    	return 1;
    }
    
    /*
    Function name : getNode
    Description : 查找节点
    Parameter   :
                 @head : 双链表的头节点
    			 @i    : 要查找的位置
    return      :返回一个数据成功,其他失败
    */
    Type getNode(Node *head, int i)
    {
    	Node *temp = head;
    	if (i<1 || i>getLength(head))return 0;/*查找位置不合法*/
    	for (int k = 0; k < i; k++)/*循环遍历将temp指针移到将要查找的节点*/
    	{
    		temp = temp->next;
    	}
    	return temp->data;/*返回数据*/
    }
    
    /*
    Function name : changeNode
    Description : 改变节点数据
    Parameter   :
                 @head : 双链表的头节点
    			 @i    : 要改变的位置
    			 @elem : 要插入的数据
    return      :返回1成功,其他失败
    */
    int changeNode(Node *head, int i, Type elem)/*改变节点数据*/
    {
    	Node *temp = head;
    	if (i<1 || i>getLength(head))return 0;/*改变位置不合法*/
    	for (int k = 0; k < i; k++)/*循环遍历将temp指针移到将要查找的节点*/
    	{
    		temp = temp->next;
    	}
    	temp->data = elem;
    	return 1;
    }
    
    int main()
    {
    	Node *head = creatListHead();/*头插法创建链表*/
    	printfList(head);/*输出*/
    	Node *head1 = creatListTail();/*尾插法创建链表*/
    	printfList(head1);
    
    	printf("增:\n");
    	insertNode(head, 1, 11);/*第1个位置插入11*/
    	printfList(head);
    	insertNode(head, 3, 33);/*中间位置插入33*/
    	printfList(head);
    	insertNode(head, 8, 99);/*最后位置插入99*/
    	printfList(head);
    
    	printf("删:\n");
    	deleteNode(head, 1);/*删除第1个*/
    	printfList(head);
    
    	deleteNode(head, 5);/*中间删除*/
    	printfList(head);
    
    	deleteNode(head, 6);/*删除最后元素*/
    	printfList(head);
    
    	printf("查:\n");
    	printf("%d\n", getNode(head, 1));/*查找第1个*/
    
    	printf("%d\n", getNode(head, 3));/*查找中间*/
    
    	printf("%d\n", getNode(head, 5));/*查找最后*/
    
    	printf("改:\n");
    	changeNode(head, 1, 88);/*改变第1个*/
    	printfList(head);
    
    	changeNode(head, 3, 77);/*改变中间*/
    	printfList(head);
    
    	changeNode(head, 5, 66);/*改变最后*/
    	printfList(head);
    	return 0;
    }
    

    在这里插入图片描述
    ok,运行成功。
    如有不足和建议,欢迎指正和讨论。亦或者有不懂的地方,欢迎评论,笔者会一一答复。后续会将所有的数据结构用c语言和java语言实现。

    展开全文
  • C语言实现数据结构——哈夫曼编码

    千次阅读 2020-11-22 15:54:39
    哈夫曼编码前言哈夫曼树与哈夫曼编码介绍思路哈夫曼树的建立对外部结点进行哈夫曼编码代码实现勉强算是总结 前言 又快一周没有更新了,最近事情比较多,回家几天拖欠了一些作业和实验,所以最近小杨在疯狂的补作业和...
  • 注意集合中只存储了指针,没有储存实际的数据。 对于新的数据类型来说,需要自定义HashCode函数和equal函数。 下面还给出了几个常见的hashCode函数和equal函数。 (1)HashCode函数 头文件
  • 这是在通用链表的基础上...注意映射中只存储了key和value的指针,没有储存实际的数据。 对于新的key类型来说,需要自定义HashCode函数和equal函数。 在HashSet的实现中给出了几个常见的hashCode函数和equal函数
  • c语言实现数据结构——单链表

    千次阅读 2020-11-08 03:49:28
    用通俗的语言来说,单链表就像是头和尾没有连接起来的自行车链,每一个节点都是独立的,却又相互联系。 创建链表 1.头插法: (1)为了操作方便,一般情况下,链表的头节点是不存放数据的。 (2)如果输入1 2 3 4,...
  • 前言最近回顾一下数据结构的相关知识什么是链表简而言之,链表由多个节点离散分配,并通过指针相互连接,并且每个节点只有一个先前节点和后续节点. 第一个节点没有前任节点,这是一个存储结构,其中节点没有后继节点...
  • 这是在通用链表的基础上实现的队列,关于链表的实现参见:... 注意队列中只存储了指针,没有储存实际的数据。  头文件 myQueue.h #ifndef MYQUEUE_H_INCLUDED #define MYQUEUE_H_INCLUDED #include
  • 约瑟夫环(持有密码版和经典版)【C语言实现】 约瑟夫环最开始的是没有密码的,如果有密码的话,约瑟夫和朋友是无法预测最后两个到底是哪两个位置的。 现在,我们改编一下约瑟夫环,改成每个人手中都持有密码。 ...
  • C语言编写的数据结构和算法实现的注释集,以及我在编写它们时记下的一些注释。 重要的提示 每个主要功能都是空的,我没有提供测试用例和数据,因为我更专注于ds / algo的实现。 我很懒惰,我不得不承认这一点:DI...
  • [数据结构]C语言链表实现http://www.cnblogs.com/racaljk/p/7822311.html 目录   静态单链表实现   动态单链表实现   双向链表实现   循环单链表 我学数据结构的时候也是感觉很...
  • 这是在通用链表的基础上实现的映射,关于链表的实现参见:...注意映射中只存储了key和value的指针,没有储存实际的数据。 对于新的key类型来说,需要自定义Ha
  • 这是在通用链表的基础上实现的椎栈,关于链表的实现参见:...注意椎栈中只存储了指针,没有储存实际的数据。 头文件: /************************* *** File myStack.h ***************
  • C语言数据结构链表队列的实现 1.写在前面  队列是一种和栈相反的,遵循先进先出原则的线性表。  本代码是严蔚敏教授的数据结构书上面的伪代码的C语言实现代码。  分解代码没有包含在内的代码如下: #include #...
  • 基于C语言的通用数据结构和算法库

    千次阅读 2015-07-02 12:04:34
    本人最近在学习数据结构的...C语言没有像C++那样的STL库,语言本身并不是一种真正意义上的高级语言,实现项目中真正用到的算法中的C语言的数据结构也很少,要么是按照自己的需求来实现,要么一般都用C++来完成大型的项
  • 这是在通用链表的基础上...注意集合中只存储了指针,没有储存实际的数据。 对于新的数据类型来说,需要自定义HashCode函数和equal函数。 下面还给出了几个常见的hashCode函数和equal函数。 (1)HashCode函数 头文件
  • C语言实现数据结构中的顺序栈

    千次阅读 2007-04-15 14:00:00
    栈(Stack)是限制仅在表的一端进行插入和删除运算...栈是后进先出(last in first out)的线性表 下面是C语言实现数据结构中的顺序栈及基本算法# include # include /*定义顺序栈*/# define StackSize 100 //假定预分配
  • 最近在复习数据结构的相关知识,感觉在初学的时候还是有很多东西没有掌握,不过现在终于算是搞得比较有头绪了,所以就在写出来和大家一起分享! 什么是链表 简单的说,链表就是由多个结点离散分配,彼此通过指针...
  • C语言数据结构链表队列的实现1.写在前面队列是一种和栈相反的,遵循先进先出原则的线性表。本代码是严蔚敏教授的数据结构书上面的伪代码的C语言实现代码。分解代码没有包含在内的代码如下:#include #include #...
  • C语语言言 数数据据结结构构之之链链表表实实现现代代码码前前言言最近在复习数据结构的相关知识,感觉在初学的时候 是有很多东西没有掌握,不过现在终于算是搞得比较有头绪了,所以就在写出来和大家一起分享!...
  • 第11章动态数据结构C语言实现 常见的内存错误及其解决对策 第11章 动态数据结构C语言实现 常见的内存错误及其对策 分类 1内存分配未成功却使用了它 2内存分配成功但尚未初始化就引用它 3内存分配成功且已初始化...
  • 有始有终,所以我准备把各种数据结构都讲一次,栈也分顺序存储和链式储存,这里我们选择链式存储来讲,顺序存储没有难度(链式其实也是)作为数据结构中最简单的栈,这里不会说太多,首先考虑一下下面的model: 这就是...
  • 题目:设计并实现一个集合数据结构Set。一个集合中没有重复元素,支持下列运算: boolean add(E o) 如果 set 中尚未存在指定的元素o,则添加此元素。 boolean addAll(Set c) 如果 set 中没有指定集合c中的...
  • 文章来源:http://blog.seclibs.com/数据结构之循环链表-c语言实现/ 之前在链表那一节说了单链表、双向链表和循环链表,前面已经把单链表和双向链表用代码实现过了,当时没有实现循环链表是在实现的过程中有一点没有...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,257
精华内容 502
关键字:

c语言没有实现数据结构

c语言 订阅
数据结构 订阅