关于顺序表和链表
2. 实验内容
在有序表中实现如下操作：
1) 插入一个新元素到第i 个位置。
2) 删除第i 个位置的元素。
3) 存一个新元素到第i 个位置。
4) 显示有序表中所有元素的值。
5）检索表中第i 个元素。
6）求表的长度。
3. 要求
分别用顺序表和链表实现
[解决办法]
http://topic.csdn.net/u/20111203/22/80e57f27-88e6-47a6-8aea-0fb35415623a.html
回复最下面那个可能就是你要的答案
[解决办法]
下面代码，楼主参考下：
/* * ccListEx.h * c++_mac_proj * * Created by xichen on 12-2-10. * Copyright 2012 cc_team. All rights reserved. * */#ifndef CC_LIST_EX_H#define CC_LIST_EX_H#include <cstdio>#include <cstdlib>#include <iostream>using namespace std;typedef struct CCListNode{ int data; struct CCListNode *next;}CCListNode, *PCCListNode, **PPCCListNode;class CCListEx {public: explicit CCListEx(PCCListNode head = NULL); ~CCListEx(); public: int count() const; PCCListNode head() const; PCCListNode getNodeAt(int index) const; // start from 0 int getIndexByNode(PCCListNode node) const; int getDataAt(int index) const; // start from 0 void setDataAt(int index, int data); // start from 0 void setNodeAt(int index, PCCListNode newNode); // start from 0 public: bool insert(int index, PCCListNode node); bool insert(PCCListNode node, int index); void insertArr(int index, PPCCListNode pNode, int cnt); void insertArr(PPCCListNode pNode, int index, int cnt); void deleteNode(int index); void deleteNode(PCCListNode node); void deleteNode(int start, int cnt); void removeAll(); void resetDataToZero(); void resetDataTo(int newData); void resetToHead(); public: friend bool operator==(const CCListEx &leftList, const CCListEx &rightList); friend bool operator!=(const CCListEx &leftList, const CCListEx &rightList); friend bool operator<(const CCListEx &leftList, const CCListEx &rightList); friend bool operator>(const CCListEx &leftList, const CCListEx &rightList);public: void reverse(); void mergeWithList(const CCListEx &anotherList); CCListEx constMergeWithList(const CCListEx &anotherList) const;public: void sort(); void sortDataArr(int arr[], int cnt) const; void sortByDescend(); private: CCListEx(const CCListEx &list); CCListEx &operator=(const CCListEx &list); private: PCCListNode _head; int _cnt;};#endif
[解决办法]
/* * ccListEx.cpp * c++_mac_proj * * Created by xichen on 12-2-10. * Copyright 2012 cc_team. All rights reserved. * */#include "ccListEx.h"CCListEx::CCListEx(PCCListNode head){ _head = NULL; _cnt = 0; if(head == NULL) return; PCCListNode node = (PCCListNode)malloc(sizeof(CCListNode)); if(node) { node->data = head->data; node->next = NULL; _head = node; ++_cnt; } else throw std::bad_alloc();}CCListEx::~CCListEx(){ PCCListNode temp = _head; PCCListNode next; while(temp) { next = temp->next; free(temp); temp = next; }}int CCListEx::count() const{ return _cnt;}PCCListNode CCListEx::head() const{ return _head;}PCCListNode CCListEx::getNodeAt(int index) const // start from 0{ PCCListNode node = _head; while(index-- > 0) node = node->next; return node;}int CCListEx::getIndexByNode(PCCListNode node) const{ PCCListNode temp = _head; int i = 0; while (temp) { if(temp == node) break; temp = temp->next; ++i; } return i;}void CCListEx::setNodeAt(int index, PCCListNode newNode) // start from 0{ PCCListNode node = getNodeAt(index); PCCListNode newNodeCopy = (PCCListNode)malloc(sizeof(CCListNode)); newNodeCopy->data = newNode->data; PCCListNode prev; PCCListNode next; if(index == 0) { next = node->next; free(node); _head = newNode; _head->next = next; } else if(index == _cnt) { prev = getNodeAt(index - 1); free(node); prev->next = newNode; newNode->next = NULL; } else { prev = getNodeAt(index - 1); next = getNodeAt(index + 1); free(node); prev->next = newNode; newNode->next = next; }}int CCListEx::getDataAt(int index) const // start from 0{ return ((PCCListNode)getNodeAt(index))->data;}void CCListEx::setDataAt(int index, int newData) // start from 0{ ((PCCListNode)getNodeAt(index))->data = newData;}bool CCListEx::insert(int index, PCCListNode newNode){ PCCListNode newNodeCopy = (PCCListNode)malloc(sizeof(CCListNode)); if(!newNodeCopy) return false; newNodeCopy->data = newNode->data; if(index == 0) { PCCListNode node = getNodeAt(index); _head = newNodeCopy; newNodeCopy->next = node; } else if(index == _cnt) { PCCListNode node = getNodeAt(index - 1); node->next = newNodeCopy; newNodeCopy->next = NULL; } else { PCCListNode node = getNodeAt(index); PCCListNode prevNode = getNodeAt(index - 1); PCCListNode nextNode = node->next; prevNode->next = newNodeCopy; newNodeCopy->next = nextNode; } ++_cnt; return true;}bool CCListEx::insert(PCCListNode node, int index){ return insert(index, node);}void CCListEx::insertArr(int index, PPCCListNode pNode, int cnt){ while(cnt--) { PCCListNode node = *(pNode + cnt); insert(node, index++); }}void CCListEx::insertArr(PPCCListNode pNode, int index, int cnt){ insertArr(index, pNode, cnt);}void CCListEx::deleteNode(int index){ PCCListNode node = getNodeAt(index); if(index == 0) { _head = node->next; } else if(index == _cnt - 1) { PCCListNode prev = getNodeAt(index - 1); prev->next = NULL; } else { PCCListNode prev = getNodeAt(index - 1); PCCListNode next = getNodeAt(index + 1); prev->next = next; } free(node); --_cnt;}void CCListEx::deleteNode(PCCListNode node){ deleteNode(getIndexByNode(node));}void CCListEx::deleteNode(int start, int cnt){ PCCListNode startNode = getNodeAt(start); PCCListNode startPrev; if(start != 0) startPrev = getNodeAt(start - 1); PCCListNode lastNode = getNodeAt(start + cnt - 1 >= _cnt ? _cnt - 1 : start + cnt - 1); PCCListNode lastNodeNext = lastNode->next; PCCListNode deleteNode = startNode; while(cnt--) { PCCListNode temp = deleteNode->next; free(deleteNode); deleteNode = temp; } if(start == 0) { _head = deleteNode; } else { startPrev->next = lastNodeNext; }}void CCListEx::removeAll(){ deleteNode(0, _cnt);}void CCListEx::resetDataToZero(){ resetDataTo(0);}void CCListEx::resetDataTo(int newData){ PCCListNode node = _head; while (node) { node->data = newData; node = node->next; }}void CCListEx::resetToHead(){ PCCListNode node = _head->next; while (node) { PCCListNode temp = node->next; free(node); node = temp; } _head->next = NULL; _cnt = 1;}void CCListEx::reverse(){ if(_cnt <= 1) return; PCCListNode curr = _head; PCCListNode next = curr->next; if(_cnt == 2) { next->next = curr; curr->next = NULL; _head = next; return; } PCCListNode nextNext = next->next; while(next) { next->next = curr; if(nextNext) nextNext->next = next; else { _head = next; break; } curr = next; next = nextNext; }}void CCListEx::mergeWithList( const CCListEx &anotherList ){ // not implement}CCListEx CCListEx::constMergeWithList( const CCListEx &anotherList ) const{ // not implement return CCListEx(NULL);}void CCListEx::sort(){ // not implement}void CCListEx::sortDataArr( int arr[], int cnt ) const{ // not implement}void CCListEx::sortByDescend(){ // not implement}bool operator==( const CCListEx &leftList, const CCListEx &rightList ){ if(leftList.count() != rightList.count()) return false; if(leftList.count() == 0 && rightList.count() == 0) return true; PCCListNode left = leftList.getNodeAt(0); PCCListNode right = rightList.getNodeAt(0); while(left != NULL && left->data == right->data) { left = left->next; right = right->next; } return (left == NULL);}bool operator!=( const CCListEx &leftList, const CCListEx &rightList ){ return !(leftList == rightList);}bool operator<( const CCListEx &leftList, const CCListEx &rightList ){ int leftCount = leftList.count(); int rightCount = rightList.count(); if(leftCount > rightCount) return false; if(leftCount == 0 && rightCount == 0) return false; if(leftCount == 0 && rightCount > 0) return true; if(leftCount > 0 && rightCount == 0) return false; PCCListNode leftNode = leftList.getNodeAt(0); PCCListNode rightNode = rightList.getNodeAt(0); while(leftNode && rightNode) { if(leftNode->data >= rightNode->data) return false; } return true;}bool operator>( const CCListEx &leftList, const CCListEx &rightList ){ int leftCount = leftList.count(); int rightCount = rightList.count(); if(leftCount < rightCount) return false; if(leftCount == 0 && rightCount == 0) return false; if(leftCount == 0 && rightCount > 0) return false; if(leftCount > 0 && rightCount == 0) return true; PCCListNode leftNode = leftList.getNodeAt(0); PCCListNode rightNode = rightList.getNodeAt(0); while(leftNode && rightNode) { if(leftNode->data <= rightNode->data) return false; } return true;}