数据结构之单链表操作(一)
链表和数组作为算法中的两个基本数据结构,在程序设计过程中经常用到。尽管两种结构都可以用来存储一系列的数据,但又各有各的特点。
1,数组的优势,在于可以方便的遍历查找需要的数据。在查询数组指定位置(如查询数组中的第4个数据)的操作中,只需要进行1次操作即可,时间复杂度为O(1)。但是,这种时间上的便利性,是因为数组在内存中占用了连续的空间,在进行类似的查找或者遍历时,本质是指针在内存中的定向偏移。然而,当需要对数组成员进行添加和删除的操作时,数组内完成这类操作的时间复杂度则变成了O(n)。
2,链表的特性,使其在某些操作上比数组更加高效。例如当进行插入和删除操作时,链表操作的时间复杂度仅为O(1)。另外,因为链表在内存中不是连续存储的,所以可以充分利用内存中的碎片空间。除此之外,链表还是很多算法的基础,最常见的哈希表就是基于链表来实现的。基于以上原因,我们可以看到,链表在程序设计过程中是非常重要的。本文总结了我们在学习链表的过程中碰到的问题和体会。
链表的定义:
typedef struct Node {
int data;
struct Node* next;
}Node;
1,头插:
代码如下:
Node* Insert_Last (Node* head ,int data)
{
// 判断数据传入是否正确
if (NULL == head)
{
return NULL;
}
// 创建新结点并判断创建是否成功
Node* node = (Node*) malloc(sizeof(Node) / sizeof(char));
if (NULL == node)
{
return NULL;
}
// 给结点成员变量赋值
Node* p = head;
node->data = data;
node->next = p->next; // 和头指针的不同:node->next = *h;
// 让新结点变为链表的第一个节点
p->next = node;
return head;
}
2,尾插
代码如下:
Node* Insert_Last(Node* head, int data)
{
if (NULL == head)
{
return NULL;
}
// 创建新结点并判断创建是否成功
Node* node = (Node*) malloc(sizeof(Node) / sizeof(char));
if (NULL == node)
{
return NULL;
}
// 给结点成员变量赋值
node->data = data;
node->next = NULL;
// 让新结点变为链表的最后一个节点
Node* tmp = head;
while(tmp->next)
{
tmp = tmp->next;
}
//找到链表的尾节点并令尾节点指向node
tmp->next = node;
return head;
}
3,查找数据节点
Node* SearchByNode(Node* head, int num)
{
Node* pHead = head;
while (pHead)
{
if (pHead->data == num)
{
return pHead;
}
pHead = pHead->pNext;
}
return NULL;
}
4,删除数据节点
Node *del(Node *head,int num)//删除一个节点
{
Node *p,*p1;
p=head;
if(head==NULL)//当链表为空时
{
printf("this table is null\n");
goto end;
}
while(num!=p->num&&p->next!=NULL)//判断链表中是否存在该结点
{
p1=p;
p=p->next;
}
if(num==p->num)//当结点存在时
{
if(p==head)
head=p->next;
else
p1->next=p->next;
printf("delete\n");
}
else
printf("not find");//找不到该结点时
return head;
}
5,更新节点数据
在这里插入代码片
6,遍历输出节点数据
void print_list(Node* head)
{
Node* p; //节点声明
p = head; //将pointer节点设为首节点
while(p != NULL)
{
printf("Data number = %d\n", p->num);
p = p->next;
}
}
7,选择排序
Node* SelectSort(Node *head)
{
Node *pfirst; /* 排列后有序链的表头指针 */
Node *ptail; /* 排列后有序链的表尾指针 */
Node *pminBefore; /* 保留键值更小的节点的前驱节点的指针 */
Node *pmin; /* 存储最小节点 */
Node *p; /* 当前比较的节点 */
pfirst = NULL;
/*1,在链表中找键值最小的节点。*/
while (head != NULL)
{
/* 注意:这里for语句就是体现选择排序思想的地方 */
for (p = head, pmin = head; p->next != NULL; p = p->next) /*循环遍历链表中的节点,找出此时最小的节点。*/
{
if (p->next->data < pmin->data) /*找到一个比当前min小的节点。*/
{
pminBefore = p; /*保存找到节点的前驱节点:显然p->next的前驱节点是p。*/
pmin = p->next; /*保存键值更小的节点。*/
}
}
/*上面for语句结束后,就要做两件事;一是把它放入有序链表中;二是根据相应的条件判断,安排它离开原来的链表。*/
/*第一件事*/
if (pfirst == NULL) /* 如果有序链表目前还是一个空链表 */
{
pfirst = pmin; /* 第一次找到键值最小的节点。 */
ptail = pmin; /* 注意:尾指针让它指向最后的一个节点。 */
}
else /* 有序链表中已经有节点 */
{
ptail->next = pmin; /* 把刚找到的最小节点放到最后,即让尾指针的next指向它。*/
ptail = pmin; /* 尾指针也要指向它。 */
}
/*第二件事*/
if (pmin == head) /* 如果找到的最小节点就是第一个节点 */
{
head = head->next; /* 显然让head指向原head->next,即第二个节点,就OK */
}
else /*如果不是第一个节点*/
{
pminBefore->next = pmin->next; /*前次最小节点的next指向当前pmin的next,这样就让pmin离开了原链表。*/
}
}
if (pfirst != NULL) /*循环结束得到有序链表first */
{
ptail->next = NULL; /*单向链表的最后一个节点的next应该指向NULL */
}
head = pfirst;
return head;
}
8,释放内存
void free_list(Node* head)
{
Node* p;
while(head != NULL)
{
p = head;
head = head->next;
free(p);
}
}
9,单链表逆序
Node *reserve(Node *head)
{
Node *p1,*p2,*p3;
p1=head;
p2=p1->next; // 这个结点为要移动的结点
while(p2)
{
p3=p2->next; //记录的为要移动的结点的下一个结点
p2->next=p1; //移动结点到最前
p1=p2; //移动的结点变为新表头
p2=p3; //下个结点变为要移动的结点
}
head->next=NULL; //移动完毕后head变为表尾,让它指向为空
head=p1;
return head;
}
10 单链表快速排序
//一次快排实现
Node* GetPartion(Node* pBegin, Node* pEnd)
{
int key = pBegin->key;
Node* p = pBegin;
Node* q = p->next;
while(q != pEnd)
{
if(q->key < key)
{
p = p->next;
swap(p->key,q->key);
}
q = q->next;
}
swap(p->key,pBegin->key);
return p;
}
void QuickSort(Node* pBeign, Node* pEnd)
{
if(pBeign != pEnd)
{
Node* partion = GetPartion(pBeign,pEnd);
QuickSort(pBeign,partion);
QuickSort(partion->next,pEnd);
}
}