问题描述

如何实现顺序表的各个功能?用C语言实现

/* 创建链表 */插入元素
删除元素 添加元素 获取元素 查找元素 清空链表 判断是否为空 判读是否已满

计算顺序表中元素的个数 急用

解决方案

book.h

// A collection of various macros, constants, and small functions
// used for the software examples.

// First, include all the standard headers that we need
#include <iostream>
#include <cstdlib>
#include <time.h>  // Used by timing functions

// Now all the standard names that we use
using std::cout;
using std::endl;
using std::string;
using std::ostream;

const int defaultSize = 10; // Default size

// Return true iff "x" is even
inline bool EVEN(int x) { return (x % 2) == 0; }

// Return true iff "x" is odd
inline bool ODD(int x) { return (x % 2) != 0; }

// Assert: If "val" is false, print a message and terminate
// the program
void Assert(bool val, string s) {
  if (!val) { // Assertion failed -- close the program
    cout << "Assertion Failed: " << s << endl;
    exit(-1);
  }
}

// Swap two elements in a generic array
template<typename E>
inline void swap(E A[], int i, int j) {
  E temp = A[i];
  A[i] = A[j];
  A[j] = temp;
}
// Random number generator functions

inline void Randomize() // Seed the generator
  { srand(1); }

// Return a random value in range 0 to n-1
inline int Random(int n)
  { return rand() % (n); }

// Swap two integers
inline void swap(int& i, int& j) {
  int temp = i;
  i = j;
  j = temp;
}

// Swap two char*'s
inline void swap(char* i, char* j) {
  char* temp = i;
  i = j;
  j = temp;
}

// Big enough for simple testing
#define INFINITY 9999

// Timing variables and functions
unsigned tstart = 0;  // Time at beginning of timed section

// Initialize the program timer
void Settime() { tstart = (unsigned) clock(); }

// Return the elapsed time since the last call to Settime
double Gettime() {
  unsigned tcurr = (unsigned) clock();
  return (double)(tcurr - tstart)/(double)CLOCKS_PER_SEC;
}

// Your basic int type as an object.
class Int {
private:
  int val;
public:
  Int(int input=0) { val = input; }
  // The following is for those times when we actually
  //   need to get a value, rather than compare objects.
  int key() const { return val; }
  // Overload = to support Int foo = 5 syntax
  Int operator= (int input) { val = input; return val; }
};

// Let us print out Ints easily
ostream& operator<<(ostream& s, const Int& i)
  { return s << i.key(); }
ostream& operator<<(ostream& s, const Int* i)
  { return s << i->key(); }

Link.h

 #ifndef LINK_H_INCLUDED
#define LINK_H_INCLUDED
#include<iostream>
template <typename E> class Link
{
public:
    E element;
    Link *next;

    Link(const E& elemval,Link* nextval =NULL)
    {
        element =elemval;
        next = nextval;
    }
    Link(Link* nextval = NULL)
    {
        next = nextval;
    }
};

#endif // LINK_H_INCLUDED

list.h

 #ifndef LIST_H_INCLUDED
#define LIST_H_INCLUDED
template<typename E> class List
{
private:
    void operator =(const List&){}
    List (const List&){}
public:
    List(){}
    virtual ~List(){}

    virtual void clear() =0;

    virtual void insert(const E& item) =0;

    virtual void append(const E& item) =0;

    virtual E remove() =0;

    virtual void moveToStart() =0;

    virtual void moveToEnd() =0;

    virtual void prev() =0;

    virtual void next() =0;

    virtual int length() const =0;

    virtual int currPos() const =0;

    virtual void moveToPos(int pos) =0;

    virtual const E& getValue() const =0;
};
#endif // LIST_H_INCLUDED

Llist_for5.h

#ifndef LLIST_H_INCLUDED
#define LLIST_H_INCLUDED

#include"List.h"
#include"Link.h"
#include"book.h"

template <typename E> class LList: public List<E>
{
private:
    Link<E>* head;
    Link<E>* tail;
    Link<E>* curr;
    int cnt;

    void init()
    {
        curr=tail=head=new Link<E>(0);//将head指针所指的元素的值赋值为0
        cnt=0;
    }

    void removeall()
    {
        tail->next=NULL;//删除指针时先将tail->next 赋值为NULL 其他不改动
        while(head != NULL)
        {
            curr = head;
            head = head->next;
            delete curr;
        }
    }

public:
    LList(int size=1){init();}

    ~LList(){ removeall();}

    void print() const;

    void clear() { removeall();init();}

    void insert(const E& it)
    {
        curr->next=new Link<E>(it,curr->next);
        if(tail == curr)tail = curr->next;
        cnt++;
    }

    void append(const E& it)
    {
      tail=tail->next=new Link<E>(it,head);//将tail->下一个指针指向head形成循环链表
      cnt++;
    }

    E remove()
    {
             Assert(head->next!=head,"NO element");
             E it=curr->next->element;
             Link<E>* ltemp=curr->next;

             if(tail==curr->next)
                                tail=curr;

             curr->next=curr->next->next;
             delete ltemp;
             cnt--;
             return it;

           //  else return -1;

    }

    void moveToStart()
    { curr=head;}

    void moveToEnd()
    { curr=tail;}

    void prev()
    {
         Link<E>* temp=head;
         while(temp->next!=curr)temp=temp->next;
         curr=temp;
     }

     void next()
     { curr=curr->next;}

     int length()const {return cnt;}

     int currPos() const
     {
         Link<E>* temp=head;
         int i;
         for(i=0;curr!=temp;i++)temp=temp->next;
         return i;

     }

     void moveToPos(int pos)
     {
          curr=head;
          for(int i=0;i<pos;i++)curr=curr->next;
      }

      const E& getValue() const
      {
          return curr->element;   // 变成读取当前的元素的值
        //return curr->next->element;
      }
};

#endif // LLIST_H_INCLUDED

main.cpp

#include"LList_for5.h"
#include<iostream>
using namespace std;
int main()
{
    LList<int> cycle;
    int n,m,i,cur,cnt=0;
    cin>>n>>m;
    for(i=1;i<=n;i++) { cycle.append(i); }
   // for(int i=0;i<= n;i++){cout<<cycle.getValue()<<endl;cycle.next();}
    for(i=1;;)
    {
                 if(cnt==n)break;
                 if(cycle.getValue()==0){cycle.next();}
                 if(i==m)
                 {

                        cycle.prev();
                        cur=cycle.remove();
                        cout<<cur<<endl;
                        cnt++;
                        i=0;
                 }
                 cycle.next();
                 i++;
    }

    return 0;
}

解决方案二：

以前写的代码，要是差哪样功能的话，你解决不了的话再联系我：

 #include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define err_exit(msg) (perror(msg),(exit(1)))
typedef struct node * link;
static link head=NULL;
int i=0;
struct node {
    unsigned char data;
    int count;
    link next;
};
link make_node(unsigned char data)
{
    link p;
    p=(link)malloc(sizeof(link));
    p->data=data;
    p->count=0;
    p->next=NULL;
    return p;
}
void free_node (link p)
{
    free(p);
}
link search(unsigned char data)
{
    link p;
    //int i=0;
    for(p=head;p;p=p->next){
        //p->count=i;
        if(p->data==data)
        {
            //p->count=i;
            printf("I find it at the pos[%d]n",p->count);
            return p;
        }
    }
}
/*pre insert*/
void insert(link p)
{
    p->next=head;
    head=p;
    ++i;
    p->count=i;
}
void delete(link p)
{
    link pre;
    if(p==head){
        /*'cause' p going to be ignoe or 'delete'
         *turn the head to p->next point
         */
         head=p->next;
         return ;
    }
    for(pre=head;pre;pre=pre->next)
        if(pre->next==p){
            pre->next=p->next;
            return ;
        }
}
int main(void)
{
    link p;
    p=make_node('a');
    insert(p);
    p=make_node('2');
    insert(p);
    p=make_node('1');
    insert(p);
    p=make_node('b');
    insert(p);
    search('b');
    return 0;
}

解决方案三：

参考代码：http://yun.baidu.com/s/17yIcQ

解决方案四：

我的博客 单链表

其他容器也有， 欢迎参考

解决方案五：

提供思路
删除元素,把前一个的next指向 后一个结点,把当前结点删除
添加,把新结点next指向当前的next结点,把当前位置结点next 指向新结点
获取
查找按next找
清空 把头next断掉
看头没有有next
没有满的说法吧
遍历可以查个数