02、单链表LinkList

02、单链表LinkList

linkList.h

#pragma once
typedef int DataType;
typedef struct Node {
	DataType data;
	struct Node* next;
}ListNode,*linkList;



void InitList(linkList* head);
int ListEmpty(linkList head);
ListNode* GetNode(linkList head, int i);
ListNode* LocateElem(linkList head, DataType e);
int LocatePos(linkList head, DataType e);
int InsertList(linkList head, int i, DataType e);
int DeleteList(linkList head, int i, DataType *e);
int ListLength(linkList head);
void DestoryList(linkList head);
int DelElem(linkList A, linkList B);

void PrintList(linkList head);

linkList.cpp

#include"linkList.h"
#include"cstdlib"
#include"cstdio"
void InitList(linkList* head)
{
	if ((*head = (linkList)malloc(sizeof(ListNode))) == NULL) {
		
		exit(-1);
	}
	(*head)->next = NULL;
}
int ListEmpty(linkList head) {
	if (head->next == nullptr) {
		return 1;
	}
	else {
		return 0;
	}
}
ListNode* GetNode(linkList head, int i) {
	ListNode *p;
	int j;
	if (ListEmpty(head) == 1) 
		return NULL;
	
	if (i < 1) 
		return NULL;
	j = 0;
	p = head;
	while (p->next != NULL && j < i) {
		p = p->next;
		j++;
	}
	if (j == i) {
		return p;
	}	
	else {
		return NULL;
	}
		

}
ListNode* LocateElem(linkList head, DataType e)

{
	ListNode* p;
	p = head->next;
	while (p) {
		if (p->data != e) {
			p = p->next;
		}
		else {
			break;
		}
	}
	return p;
}
int LocatePos(linkList head, DataType e)

{
	ListNode* p;
	int i;
	if (ListEmpty(head) == 1) {
		return 0;
	}
	p = head->next;
	i = 1;
	while (p) {
		if (p->data != e) {
			p = p->next;
			i++;
		}
		else {
			return i;
		}

	}
	if (!p) {
		return 0;
	}
}
int InsertList(linkList head, int i, DataType e) 
 {
	ListNode* pre, * p;
	
	int j;
	pre = head;
	j = 0;
	while (pre->next != NULL && j < i - 1) 
	
	{
		pre = pre->next;
		j++;
	}
	if (j != i - 1) {
		printf("插入的位置错误n");
		return 0;
	}
	
	if ((p = (ListNode*)malloc(sizeof(ListNode))) == NULL)
		exit(-1);
	p->data = e;

	
	p->next = pre->next;
	pre->next = p;
	return 1;
}
int DeleteList(linkList head, int i, DataType *e)

{
	ListNode *pre, *p;
	int j;
	pre = head;
	j = 0;
	while (pre->next != NULL && pre->next->next != NULL && j < i - 1) 
	
	{
		pre = pre->next;
		j++;
	}
	if (j != i - 1)
	{
		printf("删除位置有误n");
		return 0;
	}
	
	p = pre->next;
	*e = p->data;

	
	pre->next = p->next;
	free(p);

}
int ListLength(linkList head) {
	ListNode* p;
	p = head;
	int count = 0;
	while (p)
	{
		p = p->next;
		count++;
	}
	return count;
}
void DestoryList(linkList head) {
	ListNode *p,*q;
	p = head;
	while (p) {
		q = p;
		p = p->next;
		free(q);
	}
}

int DelElem(linkList A, linkList B)
{
	int i, pos;
	DataType e;
	ListNode* p;
	
	for (i = 1; i <= ListLength(B); i++) {
		p = GetNode(B, i);
		if (p) {
			pos = LocatePos(A, p->data);
			if (pos > 0)
				DeleteList(A, pos, &e);
		}
	}
	return 0;
}


void PrintList(linkList head)
{
	ListNode* p;
	p = head->next;
	while (p) {
		printf("%4d", p->data);
		p = p->next;
	}
	printf("n");
}

单链表在内存中的一个情况：

单链表去重： 

 

void TestlinkList_Dele() {
    int i;
    DataType a[] = { 8,17,21,25,27,29 };
    DataType b[] = { 3,8,9,21,26,27 };
    linkList A, B;

    InitList(&A);
    InitList(&B);
    for (i = 1; i <= sizeof(a) / sizeof(a[0]); i++) {
        InsertList(A, i, a[i - 1]);
    }
    for (i = 1; i <= sizeof(b) / sizeof(b[0]); i++) {
        InsertList(B, i, b[i - 1]);
    }
    printf("链表A:n");
    PrintList(A);
    printf("链表B:n");
    PrintList(B);

    DelElem(A, B);
    printf("去重后的A:n");
    PrintList(A);
 
}

 合并链表

void MergeList(linkList A, linkList B, linkList C)
{
	ListNode* pa,*pb;
	pa = A->next;
	pb = B->next;
	int i = 1;
	while (pa && pb) {
		if (pa->data < pb->data) {
			InsertList(C, i, pa->data);
			pa = pa->next;
		}
		else {
			InsertList(C, i, pb->data);
			pb = pb->next;
		}
				
		i++;
	}
	while (pa) { 
		InsertList(C, i, pa->data);
		pa = pa->next;
		i++;
	}
	while (pb) { 
		InsertList(C, i, pb->data);
		pb = pb->next;
		i++;
	}


}

头插法反转链表

void ReverseList(linkList head,linkList out)
{
	ListNode* p;
	p = head->next;
	while (p) {
		InsertList(out, 1, p->data);
		p = p->next;
	}
}