数据结构链表

单链表 类实现

#include
using namespace std;

#define ok 0
#define error -1

class ListNode {
public:
	int data;
	ListNode* next;
	ListNode() { next = NULL; }
};

class LinkList {
public:
	ListNode* head;
	int len;

	LinkList() {
		head = new ListNode();
		len = 0;
	}
	~LinkList() {
		ListNode* p, * q;
		p = head;
		while (p != NULL) {
			q = p;
			p = p->next;
			delete q;
		}
		len = 0;
		head = NULL;
	}

	void init(int n) {
		ListNode* node = head;
		len = n;
		while (n--) {
			int num;
			cin >> num;
			ListNode* l = new ListNode;
			l->data = num;
			node->next = l;
			node = node->next;
		}
	}

	ListNode* LL_index(int i) { //获取指向第i个结点的指针，如果不存在返回NULL 
		if (i > len || i < 0)return NULL;
		ListNode* l = head;
		for (int j = 0; j < i; j++) l = l->next;
		return l;
	}

	int  LL_get(int i) { //获取第i个数据 
		if (i<1 || i>len) return -1;
		return LL_index(i)->data;//头节点不存放数据 
	}

	int LL_insert(int i, int item) {
		if (i > len + 1 || i < 1) return -1;
		ListNode* l = LL_index(i - 1);
		ListNode* ll = new ListNode;
		ll->data = item;
		ll->next = l->next;
		l->next = ll;
		len++;
		return 0;
	}
	int LL_del(int i) {
		if (i<1 || i>len) return -1;
		ListNode* l = LL_index(i - 1);
		ListNode* ll = l->next;
		l->next = ll->next;
		l = NULL;
		delete l, ll;
		len--;
		return 0;
	}
	void LL_display() {
		ListNode* p;
		p = head->next;
		while (p) {
			cout << p->data << " ";
			p = p->next;
		}
		cout << endl;
	}
};

int main() {
	int n;
	cin >> n;
	LinkList list;
	list.init(n);
	list.LL_display();
	int i, item;

	cin >> i >> item;
	if (!list.LL_insert(i, item)) list.LL_display();
	else cout << "error" << endl;

	cin >> i >> item;
	if (!list.LL_insert(i, item)) list.LL_display();
	else cout << "error" << endl;

	cin >> i;
	if (!list.LL_del(i)) list.LL_display();
	else cout << "error" << endl;

	cin >> i;
	if (!list.LL_del(i)) list.LL_display();
	else cout << "error" << endl;

	cin >> i;
	int ans = list.LL_get(i);
	if (ans != -1) cout << ans << endl;
	else cout << "error" << endl;

	cin >> i;
	ans = list.LL_get(i);
	if (ans != -1) cout << ans << endl;
	else cout << "error" << endl;
}

结点交换

bool swap(int pa, int pb) {
    if(pa<1 || pb<1 || pa>len || pb>len)
        return false;

    LNode *p=Index(pa-1),*q=Index(pb-1);

    if(p->next == q)//防止相邻节点爆炸
    {
        p->next=q->next;
        q->next=p->next->next;
        p->next->next=q;
        return true;
    }

    LNode *t = p->next;//交换pa、pb两者的前驱
    p->next = q->next;
    q->next = t;

    t = p->next->next;//交换pa、pb两者的后继
    p->next->next = q->next->next;
    q->next->next=t;

    return true;
}

int main()
{
		if (p.LL_swap(lenth, num))
		{
			p.LL_display();
		}
		else
		{
			cout << "error" << endl;
		}
 } 

删除重复元素

void LinkList::LL_del() 
{
	int num1, num2;
	
	for (int i = 1; i <= len; i++) 
	{
		num1 = LL_get(i);
		for (int j = i + 1; j <= len; j++) 
		{
			num2 = LL_get(j);
			if (num1 == num2) 
			{
				ListNode* Q, *P;
				P = LL_index(j - 1);
				Q = P->next;
				
				P->next = Q->next;
				delete Q;//原文是free(Q)
				len--;
				j--;
			}
		}
	}
	LL_display();
}

循环链表 约瑟夫环(Ver. I - A)

void init(int n) {
		ListNode* node = head;
		len = n;
		while (n--) {
			int num;
			cin >> num;
			ListNode* l = new ListNode;
			l->data = num;
			node->next = l;
			node = node->next;
		}
		node->next = head; 
	}
void LinkList::Test()
{//头节点不算数！！！
    int i;
    ListNode* p = head;
    for (i = 0; i < s - 1; i++) p = p->next;//p移动到第s个结点的前一个结点。所以第s个人开始报数就移动s-1次
        
    for(; len >= 1; len--)//len次循环，仅仅用来判断最后一个是输出空格还是换行 
    {
        if(p->next == head) p = p->next;//如果p的下一个是头结点，即p是最后一个结点，就让它指向头结点 
            
        for (int i = 0; i < k - 1; i++)//循环k-1次。k:数到k出列
        {
            p = p->next;
            if (p->next == head) p = p->next;
                
        }
        cout << p->next->data;
        if (len == 1) {
            cout << endl;
        }
        else
        {
            cout << " ";
        }
        
        p->next = p->next->next;//跳过出列的结点完成出列 *** 作 
    }
}
int main()
{
    int N, K, S;
    while (cin >> N >> K >> S)
    {
        LinkList myList;
        myList.n = N;
        myList.k = K;
        myList.s = S;
        myList.CreateList();
        myList.Test();
    }
    return 0;
}

双向链表 祖玛

#include 
#include
using namespace std;

class ListNode
{public:
    char data;
    ListNode* next;
    ListNode* prior;

    ListNode() { next = NULL; prior = NULL; }
};

class LinkList
{public:
    ListNode* head;
    int len;
    LinkList();
    ~LinkList();
    void init(char *a);
    void insert(int loc, char x);
    void display();
};

LinkList::LinkList()
{
    head = new ListNode;
    len = 0;
}

LinkList::~LinkList()
{
    ListNode* p, * q;
    p = head;
    while (p->next)
    {
        q = p->next;
        delete p;
        p = q;
    }
    delete p;
}

void LinkList::init(char *a)
{
    ListNode* p, * q;
    p = head;
    len = strlen(a);
    for (int i = 0; i < len; i++)
    {
        q = new ListNode;
        q->data = a[i];
        q->prior = p;

        p->next = q;
        p = q;
        
    }
}

void LinkList::insert(int loc, char x)
{
    //插入结点
    int temp = loc;

    //1°
    ListNode* p, * q;
    p = head;
    while (temp--)
        p = p->next;
    q = new ListNode;

    //2°
    q->data = x;
    q->next = p->next;
    q->prior = p;

    //3°
    if (p->next) p->next->prior = q;

    //4°
    p->next = q;

    len++;

//检验能否消除
        while (1)
        {
            while (q && q->data == x)
                q = q->next;
            while (p->prior && p->data == x)
                p = p->prior;

            ListNode* r = p;
            int num = 0;
            while (r && r != q)
            {
                r = r->next;
                num++;
            }
            if (num >= 4)
            {
                p->next = q;
                if (q)
                    q->prior = p;
                if (p != head)
                    x = p->data;
                else if (q)
                    x = q->data;
                len -= num - 1;
            }
            else
                break;
        }
}




void LinkList::display()
{
    if (len == 0)
    {
        cout << '-' << endl;
    }
        
    else
    {
        ListNode* p;
        p = head;
        while (p->next)
        {
            p = p->next;
            cout << p->data;
        }
        cout << endl;
    }
}

int main()
{
    LinkList myList;

    char a[1000];
    cin >> a;
    myList.init(a);

    int t;
    cin >> t;
    while(t--) 
    {
        int loc;
        char x;
        cin >> loc >> x;
        myList.insert(loc, x);
        myList.display();
    }
    return 0;
}